Parametrised complexity of satisfiability in temporal logic

DOI10.1145/3001835MaRDI QIDQ5278205zbMATH OpenOpenAlexWikidataFDO

Authors Martin Lück, Arne Meier, Irena Schindler

Publication date 13 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3001835

zbMATH Keywords

treewidthpathwidthcomputation tree logictemporal logiclinear temporal logicPost's latticeparametrised complexitytemporal depth

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)

Recommendations

• Parameterized complexity of CTL
• 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 CTL⋆

Cites work

• scientific article; zbMATH DE number 3129315 (Why is no real title available?)
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 1061261 (Why is no real title available?)
• scientific article; zbMATH DE number 1142326 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 3212004 (Why is no real title available?)
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Complexity classifications for different equivalence and audit problems for Boolean circuits
• Conjunctive query containment revisited
• Conjunctive-query containment and constraint satisfaction
• Constraint Satisfaction with Bounded Treewidth Revisited
• Constraint satisfaction with bounded treewidth revisited
• Decision procedures and expressiveness in the temporal logic of branching time
• Does Treewidth Help in Modal Satisfiability?
• Erratum to: ``The complexity of satisfiability for fragments of CTL and \(\mathrm{CTL}^\star\)
• Generalized modal satisfiability
• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• Graph structure and monadic second-order logic. A language-theoretic approach
• Modal logic
• Model Checking CTL is Almost Always Inherently Sequential
• On the parameterized complexity of default logic and autoepistemic logic
• Parameterized complexity of CTL
• Parametrized complexity theory.
• Propositional dynamic logic of regular programs
• Satisfiability problems for propositional calculi
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• The Complexity of Reasoning for Fragments of Default Logic
• The complexity of problems for quantified constraints
• The complexity of propositional linear temporal logics in simple cases
• The complexity of reasoning for fragments of autoepistemic logic
• The complexity of satisfiability for fragments of hybrid logic. I.
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic

Cited in

(4)

• Parameterised complexity of model checking and satisfiability in propositional dependence logic
• Parameterized complexity of CTL
• The computational complexity of satisfiability of temporal Horn formulas in propositional linear-time temporal logic
• On the Complexity of Temporal-Logic Path Checking

This page was built for publication: Parametrised complexity of satisfiability in temporal logic

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