On a Temporal Logic of Prefixes and Infixes.

DOI10.4230/LIPICS.MFCS.2020.21OpenAlexW3082308102MaRDI QIDQ5089182FDOQ5089182

Authors: Laura Bozzelli, Angelo Montanari, Adriano Peron, Pietro Sala 

Publication date: 18 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.21

zbMATH Keywords

complexityinterval temporal logicsatisfiabilitystar-free regular languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• The undecidability of the logic of subintervals
• A Modal Logic for Chopping Intervals
• Interval logics and \(\omega B\)-regular languages
• Adding an equivalence relation to the interval logic \(AB\bar{B}\): complexity and expressiveness
• A Road Map of Interval Temporal Logics and Duration Calculi
• Complexity hierarchies beyond elementary
• Intervals and tenses
• Checking interval properties of computations
• Title not available (Why is that?)
• Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption
• Which fragments of the interval temporal logic HS are tractable in model checking?
• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• Non-finite Axiomatizability and Undecidability of Interval Temporal Logics with C, D, and T
• B and D are enough to make the Halpern-Shoham logic undecidable

Cited In (3)

• The addition of temporal neighborhood makes the logic of prefixes and sub-intervals \textsc{ExpSpace-complete}
• Adding the relation \textit{Meets} to the temporal logic of prefixes and infixes makes it EXPSPACE-complete
• \textsc{Pspace}-completeness of the temporal logic of sub-intervals and suffixes

This page was built for publication: On a Temporal Logic of Prefixes and Infixes.

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