Polytime embedding of intuitionistic modal logics into their one-variable fragments

DOI10.1093/LOGCOM/EXAE077MaRDI QIDQ6909837zbMATH OpenFDO

Authors Mikhail Rybakov, Dmitry Shkatov

Publication date 29 October 2025

Published in Journal of Logic and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1093/LOGCOM/EXAE077

zbMATH Keywords

computational complexityintuitionistic modal logicpolynomial-time embeddingsatisfiability problemvalidity problem

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Cites work

• A general method for proving decidability of intuitionistic modal logics
• A modal analysis of staged computation
• A modal extension of intuitionist logic
• A modal perspective on the computational complexity of attribute value grammar
• Algorithmic properties of first-order superintuitionistic logics of finite Kripke frames in restricted languages
• Complexity and expressivity of propositional dynamic logics with finitely many variables
• Complexity of finite-variable fragments of EXPTIME-complete logics
• Complexity of finite-variable fragments of products with K
• Complexity of finite-variable fragments of products with non-transitive modal logics
• Complexity of finite-variable fragments of propositional modal logics of symmetric frames
• Complexity of finite-variable fragments of propositional temporal and modal logics of computation
• Complexity of intuitionistic and Visser's basic and formal logics in finitely many variables
• Complexity of intuitionistic propositional logic and its fragments
• Decidability of order-based modal logics
• scientific article; zbMATH DE number 3129315 (Why is no real title available?)
• scientific article; zbMATH DE number 4139714 (Why is no real title available?)
• scientific article; zbMATH DE number 4041866 (Why is no real title available?)
• scientific article; zbMATH DE number 1215479 (Why is no real title available?)
• scientific article; zbMATH DE number 1303434 (Why is no real title available?)
• scientific article; zbMATH DE number 2196586 (Why is no real title available?)
• scientific article; zbMATH DE number 2209833 (Why is no real title available?)
• Many-dimensional modal logics: theory and applications
• Models for normal intuitionistic modal logics
• Models for stronger normal intuitionistic modal logics
• On formulas of one variable in intuitionistic propositional calculus
• On modal logic with an intuitionistic base
• On some intuitionistic modal logics
• One-variable fragments of intermediate logics over linear frames
• The complexity of poor man's logic
• The complexity of propositional linear temporal logics in simple cases
• The decision problem of provability logic with only one atom
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter
• Varieties of monadic Heyting algebras. I

This page was built for publication: Polytime embedding of intuitionistic modal logics into their one-variable fragments

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