THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆

DOI10.1142/S0129054109006954zbMath1186.68212MaRDI QIDQ3646173

No author found.

Publication date: 19 November 2009

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexity; temporal logic; satisfiability; Post's lattice

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03B44: Temporal logic

Related Items

Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic, Complexity Assessments for Decidable Fragments of Set Theory. I: A Taxonomy for the Boolean Case*, Parametrised Complexity of Satisfiability in Temporal Logic, On the applicability of Post's lattice, The complexity of circumscriptive inference in Post's lattice, The model checking fingerprints of CTL operators

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
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Unnamed Item
• Unnamed Item