Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
From MaRDI portal
Publication:5958761
DOI10.1016/S0304-3975(00)00177-8zbMath0989.68134OpenAlexW2081744921MaRDI QIDQ5958761
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00177-8
Reasoning under uncertainty in the context of artificial intelligence (68T37) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
On point-duration networks for temporal reasoning ⋮ Extending uncertainty formalisms to linear constraints and other complex formalisms ⋮ Temporal reasoning about fuzzy intervals ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Constraint solving for interpolation ⋮ A first step towards implementing dynamic algebraic dependences ⋮ From local to global consistency in temporal constraint networks ⋮ Processing disjunctions in temporal constraint networks ⋮ Decidability of Verification of Safety Properties of Spatial Families of Linear Hybrid Automata ⋮ PTIME parametric verification of safety properties for reasonable linear hybrid automata ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Reasoning about action in polynomial time ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ The PSN tribe ⋮ From binary temporal relations to non-binary ones and back ⋮ On the consistency problem for the \(\mathcal {INDU}\) calculus ⋮ A unifying approach to temporal constraint reasoning ⋮ Adding clauses to poor man's logic (without increasing the complexity) ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ Querying temporal and spatial constraint networks in PTIME ⋮ Satisfying constraint sets through convex envelopes ⋮ Point algebras for temporal reasoning: Algorithms and complexity ⋮ Complexity classification in qualitative temporal constraint reasoning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maintaining knowledge about temporal intervals
- Real addition and the polynomial hierarchy
- An optimal k-consistency algorithm
- Temporal constraint networks
- A canonical form for generalized linear constraints
- From local to global consistency
- Reasoning about qualitative temporal information
- A unifying approach to temporal constraint reasoning
- Principles and practice of constraint programming. 2nd international workshop, PPCP '94, Rosario, Orcas Island, Washington, DC, USA, May 2-4, 1994. Proceedings
- The complexity of query evaluation in indefinite temporal constraint databases
- From local to global consistency in temporal constraint networks
- Variable Elimination for Disequations in Generalized Linear Constraint Systems
- A Sufficient Condition for Backtrack-Free Search
- Synthesizing constraint expressions
- On binary constraint problems
- Reasoning about temporal relations
