Which fragments of the interval temporal logic HS are tractable in model checking?

DOI10.1016/j.tcs.2018.04.011zbMath1429.68139OpenAlexW2797441266WikidataQ130037561 ScholiaQ130037561MaRDI QIDQ1731517

Alberto Molinari, Pietro Sala, Angelo Montanari, Laura Bozzelli, Adriano Peron

Publication date: 13 March 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11390/1130799

zbMATH Keywords

computational complexitymodel checkingtemporal logic

Mathematics Subject Classification ID

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

Related Items

A separation theorem for discrete-time interval temporal logic, \textsc{Pspace}-completeness of the temporal logic of sub-intervals and suffixes, Unnamed Item, Complexity Assessments for Decidable Fragments of Set Theory. I: A Taxonomy for the Boolean Case*, On a Temporal Logic of Prefixes and Infixes.

Uses Software

• MCMAS
• DDVerify

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• Checking interval properties of computations
• Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
• Intervals and tenses
• Duration calculus. A formal approach to real-time systems.
• The dark side of interval temporal logic: marking the undecidability border
• Expressiveness and completeness of an interval tense logic
• Temporal prepositions and their logic
• Interval Temporal Logic Model Checking: The Border Between Good and Bad HS Fragments
• Tableaux for Logics of Subinterval Structures over Dense Orderings
• mcmas: A Model Checker for Multi-agent Systems
• Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals
• “Sometimes” and “not never” revisited
• A Modal Logic for Chopping Intervals
• A propositional modal logic of time intervals
• NP trees and Carnap's modal logic
• A Decision Procedure and Complete Axiomatization of Finite Interval Temporal Logic with Projection
• Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
• The Undecidability of the Logic of Subintervals
• A Road Map of Interval Temporal Logics and Duration Calculi