• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Complexity of finite-variable fragments of products with K

Journal of Logic and Computation. 2021. Vol. 31. No. 2. P. 426-443.
Rybakov M., Shkatov D.

It is shown 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 nown 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.