Complexity of products of modal logics

Publisher Website
Google Scholar
Abstract
A relatively new way of combining modal logics is to consider their products. The main application of these product logics lies in the description of parallel computing processes. Axiomatics and decidability of the validity problem have been rather extensively investigated and many logics behave well in these respects. In this paper we look at the product construction from a computation complexity point of view. We show that in many cases there is a drastic increase in complexity, e.g., all products containing the finite S5 x S5 products as models have an NEXPTIME-hard satisfaction problem. Products with a functional modality however do not lead to an increase in complexity. For the products K x S5 and S5 x S5, we provide a matching upper bound. Key words: Computational complexity, two-dimensional modal logic, tiling.
Keywords

This publication has 0 references indexed in Scilit: