Complexity and algorithms for reasoning about time

1993/11/01 by Martin Charles Golumbic, Ron Shamir · 2 citations
Computer Science · Mathematics · #Constraint Satisfaction and Optimization #Advanced Database Systems and Queries #Logic, Reasoning, and Knowledge #Tel aviv #IBM #Citation #Computer science #Algorithm #Research center #Center (category theory) #Library science #Operations research #Mathematics #Political science #Law

paper · pdf · doi:10.1145/174147.169675

openalex publication_date 1993/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

Abstract

Temporal events are regarded here as intervals on a time line, This paper deals with problems m reasoning about such intervals when the prccisc topological relationship between them is unknown or only partially specified, This work unifies notions of interval algebras in artificial intelligence with those of interval orders and mterwd gr~phs m combmatorlcs.

Citations

• Incidence matrices and interval graphs
• Depth-First Search and Linear Graph Algorithms
• Partial orders of dimension 2
• Partially Ordered Sets

Cited by

• Horn Fragments of the Halpern-Shoham Interval Temporal Logic
• Interval graph [wikipedia]