Journal of Logic and Computation, Volume 9, Issue 2, pp. 197-214: Abstract.
Complexity of products of modal logics
Department of Computing, Imperial College, London, UK, Current address: Institute for Logic, Language and Computation, University of Amsterdam, Plantage Muidergracht 24, 1018 TV, Amsterdam, The Netherlands. E-mail: email@example.com
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
Key words: Computational complexity, two-dimensional modal logic, tiling.