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

zbMATH Open1483.68186arXiv1709.02094MaRDI QIDQ3384161FDOQ3384161

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• Title not available (Why is that?)
• 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
• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• Model checking interval temporal logics with regular expressions
• 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)