PreprintCC BY 4.0arXiv
Elementary modal logics and circuit complexity
Abstract
A modal logic is elementary if it is sound and complete with respect to an elementary class of Kripke frames. We prove that if a finitely axiomatizable modal logic L is elementary, then the validity problem for L, which asks whether a given finite Kripke frame validates L, is in the circuit complexity class uniform AC0. As an application, we construct infinitely many finitely axiomatizable K4-stable logics that are not elementary. This result provides a negative answer to Problem 6.4 in [Bezhanishvili et al., 2018] for K4-stable logics.
Related
- Uncountably many maximally consistent neighborhood complete congruential modal logics
- Intuitionistic and Constructive Modal Logics for Classical Modal Logicians
- Intuitionistic Implication in Elementary Team Logics
- Closure Semantics for Weak Modal Logics: Completeness and Representations
- Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
BibTeX
@misc{takahashi2026elementary,
title = {{Elementary modal logics and circuit complexity}},
author = {Tenyo Takahashi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.10872},
eprint = {2609.10872},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10872},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Elementary modal logics and circuit complexity
AU - Tenyo Takahashi
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.10872
UR - https://arxiv.org/abs/2609.10872
AB - A modal logic is elementary if it is sound and complete with respect to an elementary class of Kripke frames. We prove that if a finitely axiomatizable modal logic L is elementary, then the validity problem for L, which asks whether a given finite Kripke frame validates L, is in the circuit complexity class uniform AC^0. As an application, we construct infinitely many finitely axiomatizable K4-stable logics that are not elementary. This result provides a negative answer to Problem 6.4 in [Bezhanishvili et al., 2018] for K4-stable logics.
ER -