Modal logics with hard diamond-free fragments

DOI10.1007/978-3-319-27683-0_1zbMATH Open1476.03021arXiv1401.5846OpenAlexW350238845MaRDI QIDQ5283414FDOQ5283414

Authors: Antonis Achilleos 

Publication date: 21 July 2017

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

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.

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

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

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)

Cites Work

• Many-dimensional modal logics: theory and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• The logic of justification
• Title not available (Why is that?)
• A guide to completeness and complexity for modal logics of knowledge and belief
• Title not available (Why is that?)
• ExpTime tableau decision procedures for regular grammar logics with converse
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Generalized modal satisfiability
• Multi-dimensional modal logic
• Title not available (Why is that?)
• Deciding regular grammar logics with converse through first-order logic
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• The complexity of poor man's logic
• The Complexity of Regularity in Grammar Logics and Related Modal Logics
• NEXP-completeness and universal hardness results for justification logic
• Modal logics with hard diamond-free fragments

Cited In (3)

• Modal logics with hard diamond-free fragments
• Modal logics with hard diamond-free fragments
• Title not available (Why is that?)

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)