Complexity of finite-variable fragments of products with non-transitive modal logics
Михаил Николаевич Рыбаков, Dmitry Shkatov · Journal of Logic and Computation · 2021
Abstract We show that products of propositional modal logics where at least one factor is one of the monomodal logics $\textbf {K}$, $\textbf {KT}$, $\textbf {KB}$ and $\textbf {KTB}$ are polynomial-time embeddable into their single-variable fragments. Consequently, we obtain results about the computational complexity of single-variable fragments of logics belonging to intervals bounded by such products. We generalize our embeddability results to expanding relativized products and to products with polymodal logics.