Parametrised Complexity of Satisfiability in Temporal Logic

DOI10.1145/3001835zbMath1367.68111OpenAlexW2582211829WikidataQ57998260 ScholiaQ57998260MaRDI QIDQ5278205

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

treewidthtemporal logicpathwidthlinear temporal logiccomputation tree 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)

Related Items

Parameterised complexity of model checking and satisfiability in propositional dependence logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• The complexity of satisfiability for fragments of hybrid logic. I.
• Constraint satisfaction with bounded treewidth revisited
• Generalized modal satisfiability
• Propositional dynamic logic of regular programs
• Conjunctive query containment revisited
• Conjunctive-query containment and constraint satisfaction
• The complexity of propositional linear temporal logics in simple cases
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• The complexity of problems for quantified constraints
• Decision procedures and expressiveness in the temporal logic of branching time
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Parametrized complexity theory.
• Parameterized Complexity of CTL
• Erratum: The Complexity of Satisfiability for Fragments of CTL and CTL^⋆
• On the Parameterized Complexity of Default Logic and Autoepistemic Logic
• The Complexity of Reasoning for Fragments of Autoepistemic Logic
• Model Checking CTL is Almost Always Inherently Sequential
• Complexity classifications for different equivalence and audit problems for Boolean circuits
• Constraint Satisfaction with Bounded Treewidth Revisited
• The Complexity of Reasoning for Fragments of Default Logic
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• Satisfiability problems for propositional calculi
• Does Treewidth Help in Modal Satisfiability?