Parametrised Complexity of Satisfiability in Temporal Logic
From MaRDI portal
Publication:5278205
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
treewidthtemporal logicpathwidthlinear temporal logiccomputation tree logicPost's latticeparametrised complexitytemporal depth
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)
Related Items
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?