THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆

DOI10.1142/S0129054109006954zbMath1186.68212OpenAlexW1967362250MaRDI QIDQ3646173

No author found.

Publication date: 19 November 2009

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

Full work available at URL: https://doi.org/10.1142/s0129054109006954

zbMATH Keywords

computational complexitytemporal logicsatisfiabilityPost's lattice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items (7)

Parametrised Complexity of Satisfiability in Temporal Logic ⋮ Computing sufficient and necessary conditions in CTL: a forgetting approach ⋮ On the applicability of Post's lattice ⋮ 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* ⋮ The complexity of circumscriptive inference in Post's lattice ⋮ The model checking fingerprints of CTL operators

Cites Work

• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆