Complexity analysis of a unifying algorithm for model checking interval temporal logic

DOI10.1016/J.IC.2020.104640OpenAlexW3097184372MaRDI QIDQ821561FDOQ821561

Authors: Laura Bozzelli, Angelo Montanari, Adriano Peron 

Publication date: 21 September 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11376/

Recommendations

• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• On the complexity of model checking for syntactically maximal fragments of the interval temporal logic HS with regular expressions
• 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
• Interval temporal logic model checking: the border between good and bad HS fragments

zbMATH Keywords

computational complexitymodel checkinginterval temporal logic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• Tableaux for logics of subinterval structures over dense orderings
• 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
• Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
• Title not available (Why is that?)
• “Sometimes” and “not never” revisited
• Intervals and tenses
• Checking interval properties of computations
• Title not available (Why is that?)
• Model checking for fragments of Halpern and Shoham's interval temporal logic based on track representatives
• 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
• Interval Temporal Logic Model Checking: The Border Between Good and Bad HS Fragments
• Title not available (Why is that?)
• A decidable weakening of Compass Logic based on cone-shaped cardinal directions
• Interval vs. Point Temporal Logic Model Checking
• Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption

Cited In (7)

• Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
• Title not available (Why is that?)
• Complexity analysis of a unifying algorithm for model checking interval temporal logic
• Title not available (Why is that?)
• Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
• \textsc{Pspace}-completeness of the temporal logic of sub-intervals and suffixes
• On the Complexity of Temporal-Logic Path Checking

This page was built for publication: Complexity analysis of a unifying algorithm for model checking interval temporal logic

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