Modal logics with hard diamond-free fragments

DOI10.1007/978-3-319-27683-0_1MaRDI QIDQ5283414zbMATH OpenOpenAlexFDO

Authors Antonis Achilleos

Publication date 21 July 2017

Published in Logical Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.5846

zbMATH Keywords

computational complexitylower boundsmodal logicsatisfiabilitymulti-modaldiamond-free fragments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45)

Abstract: We investigate the complexity of modal satisfiability for certain combinations of modal logics. In particular we examine four examples of multimodal logics with dependencies and demonstrate that even if we restrict our inputs to diamond-free formulas (in negation normal form), these logics still have a high complexity. This result illustrates that having D as one or more of the combined logics, as well as the interdependencies among logics can be important sources of complexity even in the absence of diamonds and even when at the same time in our formulas we allow only one propositional variable. We then further investigate and characterize the complexity of the diamond-free, 1-variable fragments of multimodal logics in a general setting.

Recommendations

• Modal logics with hard diamond-free fragments
• On the complexity of fragments of modal logics
• Complexity Results for Modal Dependence Logic
• Complexity results for modal dependence logic
• scientific article; zbMATH DE number 1612551

Cites work

• scientific article; zbMATH DE number 1612551 (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 1395652 (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
• Deciding regular grammar logics with converse through first-order logic
• ExpTime tableau decision procedures for regular grammar logics with converse
• Generalized modal satisfiability
• Many-dimensional modal logics: theory and applications
• Modal logics with hard diamond-free fragments
• Multi-dimensional modal logic
• NEXP-completeness and universal hardness results for justification logic
• The Complexity of Regularity in Grammar Logics and Related Modal Logics
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of poor man's logic
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• The logic of justification

Cited in

(3)

• Modal logics with hard diamond-free fragments
• Modal logics with hard diamond-free fragments
• scientific article; zbMATH DE number 1612551 (Why is no real title available?)

This page was built for publication: Modal logics with hard diamond-free fragments

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