Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning

DOI10.1016/S0304-3975(00)00177-8zbMath0989.68134OpenAlexW2081744921MaRDI QIDQ5958761

Manolis Koubarakis

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

zbMATH Keywords

linear constraintsglobal consistencyinterval algebraORD-Horn constraintsvariable elimination

Mathematics Subject Classification ID

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 (24)

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

This page was built for publication: Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning