The Complexity of Generalized Satisfiability for Linear Temporal Logic

DOI10.1007/978-3-540-71389-0_5zbMath1183.03016OpenAlexW2154374418MaRDI QIDQ5758057

Henning Schnoor, Heribert Vollmer, Thomas Schneider, Michael Bauland, Ilka Schnoor

Publication date: 7 September 2007

Published in: Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-71389-0_5

zbMATH Keywords

NP-completelinear temporal logicPSPACE-completecomplexity of satisfiabilityPTIME

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)

The Complexity of Linear-Time Temporal Logic Model Repair ⋮ The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I ⋮ The complexity of circumscriptive inference in Post's lattice ⋮ Generalized modal satisfiability ⋮ The complexity of propositional implication ⋮ The Complexity of Satisfiability for Fragments of CTL and CTL⋆ ⋮ The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments

This page was built for publication: The Complexity of Generalized Satisfiability for Linear Temporal Logic