×

Complexity of finite-variable fragments of products with K. (English) Zbl 07332113

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.

MSC:

03-XX Mathematical logic and foundations
68-XX Computer science
PDFBibTeX XMLCite
Full Text: DOI