{"id":"arxiv/2609.10872","url":"https://arxiv.org/abs/2609.10872","tags":["math.LO"],"score":0,"title":"Elementary modal logics and circuit complexity","domain":"math.LO","source":"arxiv","authors":["Tenyo Takahashi"],"reviews":0,"subject":"math.LO","summary":"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 $\\mathsf{AC}^0$. As an application, we construct infinitely many finitely axiomatizable $\\mathsf{K4}$-stable logics that are not elementary. This result provides a negative answer to Problem 6.4 in [Bezhanishvili et al., 2018] for $\\mathsf{K4}$-stable logics.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}