Home  Online Resources  Table of Contents

Journal of Logic and Computation, Volume 9, Issue 2, pp. 197-214: Abstract.

Complexity of products of modal logics

M Marx

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: marx@wins.uva.nl

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.

  Full-Text PDF  (329 KB)


[ Oxford University Press]   [ Oxford Journals]   [ Comments & Feedback]   Copyright© Oxford University Press, 1999.