The dark side of interval temporal logic: marking the undecidability border

DOI10.1007/s10472-013-9376-4zbMath1325.03014OpenAlexW1970275850MaRDI QIDQ2251125

Dario Della Monica, Davide Bresolin, Angelo Montanari, Guido Sciavicco, Valentin F. Goranko

Publication date: 11 July 2014

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-013-9376-4

zbMATH Keywords

undecidabilitytiling problemsinterval temporal logic

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Undecidability and degrees of sets of sentences (03D35) Combinatorial aspects of tessellation and tiling problems (05B45) Temporal logic (03B44)

Related Items (21)

A complete classification of the expressiveness of interval logics of Allen's relations: the general and the dense cases ⋮ Complexity analysis of a unifying algorithm for model checking interval temporal logic ⋮ Checking interval properties of computations ⋮ Sub-propositional Fragments of the Interval Temporal Logic of Allen’s Relations ⋮ On the Expressiveness of the Interval Logic of Allen’s Relations Over Finite and Discrete Linear Orders ⋮ Bounded variability of metric temporal logic ⋮ Model checking interval temporal logics with regular expressions ⋮ \textsc{Pspace}-completeness of the temporal logic of sub-intervals and suffixes ⋮ Interval Temporal Logic for Visibly Pushdown Systems ⋮ Model checking for fragments of Halpern and Shoham's interval temporal logic based on track representatives ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Interval vs. Point Temporal Logic Model Checking ⋮ Unnamed Item ⋮ Which fragments of the interval temporal logic HS are tractable in model checking? ⋮ Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals ⋮ The dark side of interval temporal logic: marking the undecidability border ⋮ Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy ⋮ Unnamed Item ⋮ Interval Temporal Logic Model Checking: The Border Between Good and Bad HS Fragments ⋮ On coarser interval temporal logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
• An optimal decision procedure for right propositional neighborhood logic
• A calculus of durations
• A logical study of distributed transition systems
• The dark side of interval temporal logic: marking the undecidability border
• Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• Tableaux for Logics of Subinterval Structures over Dense Orderings
• Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders
• Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals
• B and D Are Enough to Make the Halpern–Shoham Logic Undecidable
• A propositional modal logic of time intervals
• Decidable and Undecidable Fragments of Halpern and Shoham’s Interval Temporal Logic: Towards a Complete Classification
• A Road Map of Interval Temporal Logics and Duration Calculi

This page was built for publication: The dark side of interval temporal logic: marking the undecidability border