Abstract
The complexity of the satisfiability problems of various arrow logics and cylindric modal logics is determined. As is well known, relativising these logics makes them decidable. There are several parameters that can be set in such a relativisation. We focus on the following three: the number of variables involved, the similarity type and the kind of relativised models considered. The complexity analysis shows the importance and relevance of these parameters.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
AndrÉka, H., I. Hodkinson, and I. NÉmeti, 'Finite algebras of relations are representable on finite sets', Journal of Symbolic Logic 64:243-267, 1999.
Fisher, M., and R. Ladner, 'Propositional dynamic logic of regular programs', J. Comput. Syst. Sci. 18:194-211, 1979.
GrÄdel, E., 'On the restraining power of guards', Journal of Symbolic Logic 64:1719-1742, 1999.
Halpern, J. Y., and Y. O. Moses, 'A guide to completeness and complexity for modal logics of knowledge and belief', Artificial Intelligence 54:319-379, 1992.
Ladner, R., 'The computational complexity of provability in systems of modal propositional logic', SIAM Journal of Computing 6:467-480, 1977.
Marx, M., and Sz. MikulÁs, 'Decidability of cylindric set algebras of dimension 2 and first order logic with two variables', Journal of Symbolic Logic 64:1563-1572, 1999.
Marx, M., L. PÓlos, and M. Masuch (eds.), Arrow Logic and Multimodal Logics, Studies in Logic, Language and Information, CSLI Publications, Stanford, 1996.
Marx, M., and Y. Venema, Multi-dimensional Modal Logic, Applied Logic Series, Kluwer Academic Publishers, 1997.
MikulÁs, Sz., and M. Marx, 'Undecidable relativizations of algebras of relations', Journal of Symbolic Logic 64:747-760, 1999.
NÉmeti, I., 'A fine-structure analysis of first-order logic', In M. Masuch (eds.), Arrow Logic and Multimodal Logics, Studies in Logic, Language and Information, CSLI Publications, Stanford, 1996 [7], pp. 221-247.
Spaan, E., 'Complexity of modal logics', PhD thesis, Institute for Logic, Language and Computation, University of Amsterdam, 1993.
Tarski, A., and S. Givant, A Formalization of Set Theory without Variables, AMS Colloquium Publications 41, Providence, Rhode Island, 1987.
Van Benthem, J., Modal Logic and Classical Logic, Bibliopolis, Naples, 1983.
Van Benthem, J., Exploring Logical Dynamics, Studies in Logic, Language and Information, CSLI Publications, Stanford, 1996.
Vardi, M., 'Why is modal logic so robustly decidable?', In DIMACS Series in Discrete Mathematics and Theoretical Computer Science 31, American Math. Society, 1997, pp. 149-184.
Venema, Y., 'Two-dimensional modal logics for relational algebras and temporal logic of intervals', ITLI-prepublication series LP-89-03, University of Amsterdam, 1989.
Venema, Y., 'Many-dimensional modal logic', PhD thesis, Institute for Logic, Language and Computation, University of Amsterdam, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Marx, M. Computing with Cylindric Modal Logics and Arrow Logics, Lower Bounds. Studia Logica 72, 233–252 (2002). https://doi.org/10.1023/A:1021360511488
Issue Date:
DOI: https://doi.org/10.1023/A:1021360511488