Notre Dame Journal of Formal Logic 37 (2):174-203 (1996)

We investigate the effect on the complexity of adding the universal modality and the reflexive transitive closure modality to modal logics. From the examples in the literature, one might conjecture that adding the reflexive transitive closure modality is at least as hard as adding the universal modality, and that adding either of these modalities to a multi-modal logic where the modalities do not interact can only increase the complexity to EXPTIME-complete. We show that the first conjecture holds under reasonable assumptions and that, except for a number of special cases which we fully characterize, the hardness part of the second conjecture is true. However, the upper bound part of the second conjecture fails miserably: we show that there exists a uni-modal, decidable, finitely axiomatizable, and canonical logic for which adding the universal modality causes undecidability and for which adding the reflexive transitive closure modality causes high undecidability
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1305/ndjfl/1040046086
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 58,321
Through your library

References found in this work BETA

Properties of Independently Axiomatizable Bimodal Logics.Marcus Kracht & Frank Wolter - 1991 - Journal of Symbolic Logic 56 (4):1469-1485.

Add more references

Citations of this work BETA

Why Combine Logics?Patrick Blackburn & Maarten de Rijke - 1997 - Studia Logica 59 (1):5 - 27.
Complexity of Intuitionistic Propositional Logic and its Fragments.Mikhail Rybakov - 2008 - Journal of Applied Non-Classical Logics 18 (2-3):267-292.
Zooming in, Zooming Out.Patrick Blackburn & Maarten de Rijke - 1997 - Journal of Logic, Language and Information 6 (1):5-31.

View all 10 citations / Add more citations

Similar books and articles

Democracy is a Failure Worthy of Infinite Repetition.Jon Simons - 2001 - Critical Horizons 2 (1):127-148.
Does Classicism Explain Universality?Stephen H. Phillips - 2002 - Minds and Machines 12 (3):423-434.
The Non-Modularity of Moral Knowledge.Theresa Waynand Tobin - 2005 - Social Philosophy Today 21:33-50.
The Non-Generic Universality and the XXIth Century.Viorel Guliciuc - 2008 - Proceedings of the Xxii World Congress of Philosophy 24:11-17.
Imperatives, Logic, and Moral Obligation.Robert G. Turnbull - 1960 - Philosophy of Science 27 (4):374-390.
Discourses on Information Ethics: The Claim to Universality. [REVIEW]Bernd Carsten Stahl - 2008 - Ethics and Information Technology 10 (2-3):97-108.
The Universality of Laws.John Earman - 1978 - Philosophy of Science 45 (2):173-181.
Dialogue on Price Gouging.Matt Zwolinski - 2009 - Business Ethics Quarterly 19 (2):295-303.
Intentionalism and Perceptual Presence.Adam Pautz - 2007 - Philosophical Perspectives 21 (1):495-541.
Foucault and Ethical Universality.Christopher Cordner - 2004 - Inquiry: An Interdisciplinary Journal of Philosophy 47 (6):580 – 596.


Added to PP index

Total views
2 ( #1,378,130 of 2,419,781 )

Recent downloads (6 months)
2 ( #351,015 of 2,419,781 )

How can I increase my downloads?


Sorry, there are not enough data points to plot this chart.

My notes