Parameterized modal satisfiability

DOI10.1007/S00453-011-9552-ZzbMath1283.68157OpenAlexW1985294169MaRDI QIDQ1759682

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 logicsatisfiability problemsparameterized complexity

Mathematics Subject Classification ID

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

Related Items (2)

An NP-complete fragment of fibring logic ⋮ The complexity of identifying characteristic formulae

Cites Work

• A guide to completeness and complexity for modal logics of knowledge and belief
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parameterized modal satisfiability