The Complexity of Satisfiability for Fragments of CTL and CTL⋆

DOI10.1016/j.entcs.2008.12.040zbMath1337.68134OpenAlexW2080461902WikidataQ57998331 ScholiaQ57998331MaRDI QIDQ4982095

No author found.

Publication date: 23 March 2015

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2008.12.040

zbMATH Keywords

temporal logicsatisfiabilityPost lattice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Temporal logic (03B44)

Related Items (7)

Modal logics and local quantifiers: a zoo in the elementary hierarchy ⋮ Complexity results for modal dependence logic ⋮ Intention as commitment toward time ⋮ The complexity of propositional implication ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning ⋮ A Decidable Spatial Logic with Cone-Shaped Cardinal Directions

Cites Work

• About the expressive power of CTL combinators
• Propositional dynamic logic of regular programs
• Gap-languages and log-time complexity classes
• Past is for free: On the complexity of verifying linear temporal properties with past
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• The complexity of propositional linear temporal logics
• Satisfiability problems for propositional calculi
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The Complexity of Generalized Satisfiability for Linear Temporal Logic
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Unnamed Item
• Unnamed Item

This page was built for publication: The Complexity of Satisfiability for Fragments of CTL and CTL⋆