Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
From MaRDI portal
Publication:636267
DOI10.1016/j.apal.2009.07.003zbMath1221.03022OpenAlexW2087983477MaRDI QIDQ636267
Guido Sciavicco, Davide Bresolin, Angelo Montanari, Valentin F. Goranko
Publication date: 26 August 2011
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2009.07.003
Logic in computer science (03B70) Decidability of theories and sets of sentences (03B25) 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 ⋮ On interval modal logic with ``after relation ⋮ Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\) ⋮ ON BEGINS, MEETS AND BEFORE ⋮ Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings ⋮ Checking interval properties of computations ⋮ Metric propositional neighborhood logic with an equivalence relation ⋮ A separation theorem for discrete-time interval temporal logic ⋮ Model checking interval temporal logics with regular expressions ⋮ Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers ⋮ A survey on temporal logics for specifying and verifying real-time systems ⋮ \textsc{Pspace}-completeness of the temporal logic of sub-intervals and suffixes ⋮ Model checking for fragments of Halpern and Shoham's interval temporal logic based on track representatives ⋮ Unnamed Item ⋮ Interval vs. Point Temporal Logic Model Checking ⋮ Unnamed Item ⋮ Interval temporal logics over strongly discrete linear orders: expressiveness and complexity ⋮ Which fragments of the interval temporal logic HS are tractable in model checking? ⋮ Optimal Tableau Systems for Propositional Neighborhood Logic over All, Dense, and Discrete Linear Orders ⋮ The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT ⋮ The dark side of interval temporal logic: marking the undecidability border ⋮ Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders ⋮ Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy ⋮ THE TEMPORAL LOGIC OF TWO DIMENSIONAL MINKOWSKI SPACETIME IS DECIDABLE ⋮ Interval Temporal Logic Model Checking: The Border Between Good and Bad HS Fragments ⋮ Two-sorted Point-Interval Temporal Logics ⋮ Prompt Interval Temporal Logic ⋮ FTClogic: fuzzy temporal constraint logic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An optimal decision procedure for right propositional neighborhood logic
- Definability with bounded number of bound variables
- Expressiveness and completeness of an interval tense logic
- First-order logic with two variables and unary temporal logic
- A general tableau method for propositional interval temporal logics: theory and implementation
- Two variable first-order logic over ordered domains
- Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders
- An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic
- A Modal Logic for Chopping Intervals
- On languages with two variables
- A propositional modal logic of time intervals
- On the Decision Problem for Two-Variable First-Order Logic
- Undecidability of compass logic
- Tableau Systems for Logics of Subinterval Structures over Dense Orderings
- Automated Reasoning with Analytic Tableaux and Related Methods
- A Road Map of Interval Temporal Logics and Duration Calculi
