Rybakov, Mikhail; Shkatov, Dmitry Complexity of finite-variable fragments of products with K. (English) Zbl 07332113 J. Log. Comput. 31, No. 2, 426-443 (2021). Summary: We show that products and expanding relativized products of propositional modal logics where one component is the minimal monomodal logic K are polynomial-time reducible to their single-variable fragments. Therefore, the known lower-bound complexity and undecidability results for such logics are extended to their single-variable fragments. Similar results are obtained for products where one component is a polymodal logic with a K-style modality; these include products with propositional dynamic logics. Cited in 4 Documents MSC: 03-XX Mathematical logic and foundations 68-XX Computer science Keywords:products of modal logics; expanding relativized products; finite-variable fragments; computational complexity; satisfiability problem; validity problem PDFBibTeX XMLCite \textit{M. Rybakov} and \textit{D. Shkatov}, J. Log. Comput. 31, No. 2, 426--443 (2021; Zbl 07332113) Full Text: DOI