Expressiveness and completeness of an interval tense logic
From MaRDI portal
Publication:2277246
The paper contains an investigation of some logical properties of interval-based temporal logics, in particular the system HS devised by Halpern and Shoham. With respect to expressiveness, it is shown that HS has a greater capacity to distinguish ordinals than any point-based formalism. On the other hand it is proved that no finite set of temporal operators can be expressively complete over the class of dense linear interval structures. Concerning completeness of HS-logics, sound and complete axiomatizations are provided for classes like the linear orderings, discrete linear orderings and the ordering of the rationals. An important aspect of the paper is that it treats the modal logic of intervals as a two-dimensional logic, viewing intervals as points in a plane.
Recommendations
- A complete classification of the expressiveness of interval logics of Allen's relations: the general and the dense cases
- On the expressiveness of the interval logic of Allen's relations over finite and discrete linear orders
- Interval temporal logics over finite linear orders: the complete picture
- On expressiveness of Halpern-Shoham logic and its Horn fragments
- Interval temporal logics over strongly discrete linear orders: expressiveness and complexity
Cited in
(62)- TABLEAUX: A general theorem prover for modal logics
- Finite \(H\)-dimension does not imply expressive completeness
- A note on the interpolation property in tense logic
- Duration calculus: Logical foundations
- Generalized concepts of syntactically and semantically trivial differences and instant-based and period-based time ontologies
- 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?
- 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
- Combining temporal logic systems
- An `almost classical' period-based tense logic
- Computational complexity of hybrid interval temporal logics
- Model checking interval temporal logics with regular expressions
- Expressiveness of concurrent intensionality
- The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT
- On coarser interval temporal logics
- Hybrid fragments of Halpern-Shoham logic and their expressive power
- Temporal prepositions and their logic
- A new modal logic for reasoning about space: spatial propositional neighborhood logic
- A complete classification of the expressiveness of interval logics of Allen's relations: the general and the dense cases
- A proof system for unified temporal logic
- Interval temporal logic model checking: the border between good and bad HS fragments
- A duration calculus with neighborhood modalities.
- On begins, meets and before
- On the expressiveness of the interval logic of Allen's relations over finite and discrete linear orders
- On the complexity of model checking for syntactically maximal fragments of the interval temporal logic HS with regular expressions
- A Correspondence between Temporal Description Logics
- A Decidable Spatial Logic with Cone-Shaped Cardinal Directions
- Relational dual tableaux for interval temporal logics
- Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers
- A Modal Logic for Chopping Intervals
- scientific article; zbMATH DE number 1222565 (Why is no real title available?)
- Handling database updates in two-dimensional temporal logic
- Derivation rules as anti-axioms in modal logic
- Completeness and decidability of tense logics closely related to logics above K4
- scientific article; zbMATH DE number 1163393 (Why is no real title available?)
- Hyperboolean Algebras and Hyperboolean Modal Logic
- Interval vs. point temporal logic model checking. An expressiveness comparison
- THE TEMPORAL LOGIC OF TWO DIMENSIONAL MINKOWSKI SPACETIME IS DECIDABLE
- Interval temporal logics over strongly discrete linear orders: expressiveness and complexity
- scientific article; zbMATH DE number 834565 (Why is no real title available?)
- Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption
- On temporal and separation logics
- Computational complexity of a core fragment of Halpern-Shoham logic
- \(\mathrm{FO}=\mathrm{FO}^3\) for linear orders with monotone binary relations
- An integrated first-order theory of points and intervals over linear orders. II
- A Road Map of Interval Temporal Logics and Duration Calculi
- A Road Map of Interval Temporal Logics and Duration Calculi
- Interval Temporal Logic for Visibly Pushdown Systems
- Parametric interval temporal logic over infinite words
- Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
- The addition of temporal neighborhood makes the logic of prefixes and sub-intervals \textsc{ExpSpace-complete}
- Unary and two-variable interval logics
- Interval temporal logic HS with path quantifiers
- A quantitative extension of interval temporal logic over infinite words
- Handling of past and future with Phenesthe+
- An adequate first order interval logic
- Superintuitionistic predicate logics of linear Kripke frames: undecidability with two individual variables
- Constraining cycle alternations in model checking for interval temporal logic
- Complexity analysis of a unifying algorithm for model checking interval temporal logic
- Subject-oriented spatial logic
- Algebraic neighbourhood logic
This page was built for publication: Expressiveness and completeness of an interval tense logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277246)
