On the complexity of model checking for syntactically maximal fragments of the interval temporal logic HS with regular expressions

MaRDI QIDQ3384161zbMATH OpenFDO

Authors Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron

Publication date 14 December 2021

Full work available at URL https://arxiv.org/abs/1709.02094, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GANDALF2017.3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Temporal logic (03B44)

Recommendations

• Model checking interval temporal logics with regular expressions
• Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
• An in-depth investigation of interval temporal logic model checking with regular expressions
• Interval temporal logic model checking: the border between good and bad HS fragments
• Complexity analysis of a unifying algorithm for model checking interval temporal logic

Cites work

• scientific article; zbMATH DE number 6767596 (Why is no real title available?)
• A Decision Procedure for the First Order Theory of Real Addition with Order
• A propositional modal logic of time intervals
• Alternation
• An in-depth investigation of interval temporal logic model checking with regular expressions
• Checking interval properties of computations
• Decidability of model checking multi-agent systems against a class of EHS specifications
• Expressiveness and completeness of an interval tense logic
• Interval temporal logic model checking: the border between good and bad HS fragments
• Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
• Intervals and tenses
• Maintaining knowledge about temporal intervals
• Model checking the logic of Allen's relations \textit{Meets} and \textit{Started-by} is \(\mathbf{P}^{\mathbf{NP}}\)-complete
• On the complexity of model checking for syntactically maximal fragments of the interval temporal logic HS with regular expressions
• Temporal prepositions and their logic
• The complexity of one-agent refinement modal logic
• The dark side of interval temporal logic: marking the undecidability border
• The undecidability of the logic of subintervals
• mcmas: A Model Checker for Multi-agent Systems
• “Sometimes” and “not never” revisited

Cited in

(12)

• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• scientific article; zbMATH DE number 7577569 (Why is no real title available?)
• Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
• Interval vs. point temporal logic model checking. An expressiveness comparison
• On the complexity of model checking for syntactically maximal fragments of the interval temporal logic HS with regular expressions
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• Model checking interval temporal logics with regular expressions
• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• Modal logics and local quantifiers: a zoo in the elementary hierarchy
• An in-depth investigation of interval temporal logic model checking with regular expressions
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• On Composing Finite Forests with Modal Logics

This page was built for publication: On the complexity of model checking for syntactically maximal fragments of the interval temporal logic HS with regular expressions

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