A fast algorithm and Datalog inexpressibility for temporal reasoning

DOI10.1145/1740582.1740583MaRDI QIDQ2946603zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Jan Kára

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.1473

zbMATH Keywords

algorithmscomputational complexityconstraint satisfactionDatalogOrd-Hornprecedence constraintstemporal reasoning

Mathematics Subject Classification ID

Logic programming (68N17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic in artificial intelligence (68T27)

Abstract: We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) this language cannot be solved by Datalog or by establishing local consistency.

Recommendations

• A unifying approach to temporal constraint reasoning
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Qualitative temporal and spatial reasoning revisited
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
• Tractable approximations for temporal constraint handling

Cited in

(8)

• A unifying approach to temporal constraint reasoning
• Constants and finite unary relations in qualitative constraint reasoning
• Relation algebras of Sugihara, Belnap, Meyer, and Church
• Tractability frontier for dually-closed Ord-Horn quantified constraint satisfaction problems
• Tractability of quantified temporal constraints to the max
• On the descriptive complexity of temporal constraint satisfaction problems
• Complexity classification transfer for CSPs via algebraic products
• Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: A fast algorithm and Datalog inexpressibility for temporal reasoning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946603)