Parameterized modal satisfiability

DOI10.1007/S00453-011-9552-ZMaRDI QIDQ1759682zbMATH OpenOpenAlexFDO

Authors Antonis Achilleos, Michael Lampis, Valia Mitsou

Publication date 21 November 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-58600

zbMATH Keywords

modal logicparameterized complexitysatisfiability problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Parameterized modal satisfiability
• Does treewidth help in modal satisfiability? (Extended abstract)
• Does Treewidth Help in Modal Satisfiability?
• Generalized modal satisfiability
• Generalized Modal Satisfiability

Cites work

• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 757645 (Why is no real title available?)
• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• scientific article; zbMATH DE number 5794052 (Why is no real title available?)
• scientific article; zbMATH DE number 2196586 (Why is no real title available?)
• A guide to completeness and complexity for modal logics of knowledge and belief
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
• Handbook of modal logic
• On the complexity of fragments of modal logics
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of first-order and monadic second-order logic revisited
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(7)

• The complexity of identifying characteristic formulae
• Generalized Modal Satisfiability
• Parameterized modal satisfiability
• Does treewidth help in modal satisfiability? (Extended abstract)
• scientific article; zbMATH DE number 67510 (Why is no real title available?)
• An NP-complete fragment of fibring logic
• Modal Satisfiability via SMT Solving

This page was built for publication: Parameterized modal satisfiability

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