Complexity of finite-variable fragments of propositional modal logics of symmetric frames

DOI10.1093/JIGPAL/JZY018MaRDI QIDQ5241916zbMATH OpenOpenAlexWikidataFDO

Authors Mikhail Rybakov, Dmitry Shkatov

Publication date 4 November 2019

Published in Logic Journal of the IGPL (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityfinite-variable fragmentspropositional modal logicsymmetric frames

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: While finite-variable fragments of the propositional modal logic S5--complete with respect to reflexive, symmetric and transitive frames--are polynomial-time decidable, the restriction to finite-variable formulas for logics of reflexive and transitive frames yields fragments that remain "intractable." The role of the symmetry condition in this context has not been investigated. We show that symmetry either by itself or in combination with reflexivity produces logics that behave just like logics of reflexive and transitive frames, i.e. their finite-variable fragments remain intractable, namely PSPACE-hard. This raises the question of where exactly the borderline lies between modal logics whose finite-variable fragments are tractable and the rest.

Recommendations

• Complexity of finite-variable fragments of EXPTIME-complete logics
• Complexity and expressivity of propositional dynamic logics with finitely many variables
• scientific article; zbMATH DE number 2196586
• Modal logics with hard diamond-free fragments
• On the complexity of fragments of modal logics

Cited in

(13)

• Computational complexity for bounded distributive lattices with negation
• Complexity of finite-variable fragments of propositional temporal and modal logics of computation
• Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter
• Computational complexity of the word problem in modal and Heyting algebras with a small number of generators
• Complexity of finite-variable fragments of EXPTIME-complete logics
• Symmetries in modal logics
• Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
• Complexity of finite-variable fragments of products with non-transitive modal logics
• Complexity through translations for modal logic with recursion
• Complexity results for modal logic with recursion via translations and tableaux
• Polytime embedding of intuitionistic modal logics into their one-variable fragments
• Algorithmic properties of modal and superintuitionistic logics of monadic predicates over finite Kripke frames
• Variations on the Kripke trick

This page was built for publication: Complexity of finite-variable fragments of propositional modal logics of symmetric frames

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