Maximal decidable fragments of Halpern and Shoham's modal logic of intervals

DOI10.1007/978-3-642-14162-1_29MaRDI QIDQ3587451zbMATH OpenOpenAlexFDO

Authors Angelo Montanari, Gabriele Puppis, Pietro Sala

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14162-1_29

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25)

Recommendations

• Decidability of the interval temporal logic \(\mathsf{A}\bar{\mathsf{A}}\mathsf{B}\bar{\mathsf{B}}\) over the rationals
• The dark side of interval temporal logic: marking the undecidability border
• Begin, after, and later: a maximal decidable interval temporal logic
• On begins, meets and before
• Interval temporal logics over finite linear orders: the complete picture

Cited in

(30)

• A complete classification of the expressiveness of interval logics of Allen's relations: the general and the dense cases
• Which fragments of the interval temporal logic HS are tractable in model checking?
• The Parametric Complexity of Lossy Counter Machines
• Model checking for fragments of Halpern and Shoham's interval temporal logic based on track representatives
• Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals
• Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
• An interval temporal logic characterization of extended \(\omega\)-regular languages
• Hybrid metric propositional neighborhood logics with interval length binders
• Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\)
• The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT
• B and D are enough to make the Halpern-Shoham logic undecidable
• Interval temporal logics over strongly discrete linear orders: expressiveness and complexity
• On coarser interval temporal logics
• Extracting interval temporal logic rules: a first approach
• On the expressiveness of the interval logic of Allen's relations over finite and discrete linear orders
• The undecidability of the logic of subintervals
• On interval modal logic with ``after relation
• Checking interval properties of computations
• The dark side of interval temporal logic: marking the undecidability border
• Model checking the logic of Allen's relations \textit{Meets} and \textit{Started-by} is \(\mathbf{P}^{\mathbf{NP}}\)-complete
• Optimal tableau systems for propositional neighborhood logic over all, dense, and discrete linear orders
• Decidability of the interval temporal logic \(\mathsf{A}\bar{\mathsf{A}}\mathsf{B}\bar{\mathsf{B}}\) over the rationals
• Two-sorted point-interval temporal logics
• On begins, meets and before
• Reactive synthesis from interval temporal logic specifications
• Begin, after, and later: a maximal decidable interval temporal logic
• Sub-propositional fragments of the interval temporal logic of Allen's relations
• Complexity hierarchies beyond elementary
• Interval-based temporal functional dependencies: specification and verification
• Interval-based synthesis

This page was built for publication: Maximal decidable fragments of Halpern and Shoham's modal logic of intervals

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