Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
From MaRDI portal
Publication:636267
DOI10.1016/j.apal.2009.07.003zbMath1221.03022MaRDI 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
03B70: Logic in computer science
03B25: Decidability of theories and sets of sentences
03B44: Temporal logic
Related Items
Interval vs. Point Temporal Logic Model Checking, THE TEMPORAL LOGIC OF TWO DIMENSIONAL MINKOWSKI SPACETIME IS DECIDABLE, Unnamed Item, Unnamed Item, Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders, A separation theorem for discrete-time interval temporal logic, \textsc{Pspace}-completeness of the temporal logic of sub-intervals and suffixes, A complete classification of the expressiveness of interval logics of Allen's relations: the general and the dense cases, Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\), Checking interval properties of computations, Metric propositional neighborhood logic with an equivalence relation, Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers, Interval temporal logics over strongly discrete linear orders: expressiveness and complexity, Complexity analysis of a unifying algorithm for model checking interval temporal logic, Model checking for fragments of Halpern and Shoham's interval temporal logic based on track representatives, Which fragments of the interval temporal logic HS are tractable in model checking?, Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy, Model checking interval temporal logics with regular expressions, 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, FTClogic: fuzzy temporal constraint logic, On interval modal logic with ``after relation, A survey on temporal logics for specifying and verifying real-time systems, Interval Temporal Logic Model Checking: The Border Between Good and Bad HS Fragments, Two-sorted Point-Interval Temporal Logics, Prompt Interval Temporal Logic, ON BEGINS, MEETS AND BEFORE, Optimal Tableau Systems for Propositional Neighborhood Logic over All, Dense, and Discrete Linear Orders, Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings
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