The dark side of interval temporal logic: marking the undecidability border
From MaRDI portal
Publication:2251125
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
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
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
