Name
Abstract | ||
|---|---|---|
We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions--for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0004-3702(03)00075-4 | Artif. Intell. |
Keywords | Field | DocType |
satisfiability problem,additional result,bounded number,different time model,tractable subclasses,new time model,tractable point algebra,spatial reasoning,temporal reasoning,point algebra,satisfiability,total order,constraint satisfaction,computational complexity,partial order | Discrete mathematics,Constraint satisfaction,Spatial intelligence,Boolean satisfiability problem,Satisfiability,Algorithm,Reasoning system,Mathematics,Bounded function,Branching (version control),Computational complexity theory | Journal |
Volume | Issue | ISSN |
149 | 2 | 0004-3702 |
Citations | PageRank | References |
20 | 1.39 | 33 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mathias Broxvall | 1 | 301 | 25.54 |
| Peter Jonsson | 2 | 700 | 54.04 |