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