The Complexity of Generalized Satisfiability for Linear Temporal Logic

DOI10.2168/LMCS-5(1:1)2009MaRDI QIDQ3623013zbMATH OpenOpenAlexFDO

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

Publication date 29 April 2009

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-5(1:1)2009

zbMATH Keywords

complexity of satisfiabilitylinear temporal logicNP-completePSPACE-completePTIME

Mathematics Subject Classification ID

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

Recommendations

• The Complexity of Generalized Satisfiability for Linear Temporal Logic
• The complexity of propositional linear temporal logics
• The complexity of clausal fragments of LTL
• The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\)
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆

Cited in

(26)

• The computational complexity of satisfiability of temporal Horn formulas in propositional linear-time temporal logic
• Backdoors for linear temporal logic
• The complexity of propositional linear temporal logics in simple cases
• Lewis dichotomies in many-valued logics
• From LTL to unambiguous Büchi automata via disambiguation of alternating automata
• On the complexity of linear temporal logic with team semantics
• The model checking fingerprints of CTL operators
• Bounded variability of metric temporal logic
• The complexity of clausal fragments of LTL
• Satisfaction degree for a class of temporal logic formulae based on transition systems
• The tractability of model checking for LTL: the good, the bad, and the ugly fragments
• A Cookbook for Temporal Conceptual Data Modelling with Description Logics
• Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
• Weak Kripke structures and LTL
• The complexity of dual models problem of propositional linear temporal logics
• The complexity of propositional linear temporal logics
• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• Towards a notion of unsatisfiable and unrealizable cores for LTL
• scientific article; zbMATH DE number 1136071 (Why is no real title available?)
• Backdoors for linear temporal logic
• The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\)
• The tractability of model-checking for LTL: the good, the bad, and the ugly fragments
• Parametrised complexity of satisfiability in temporal logic
• On the satisfiability of indexed linear temporal logics
• Developments in Language Theory
• The Complexity of Generalized Satisfiability for Linear Temporal Logic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3623013)