The bibliographic entry was discovered and compiled by a machine, and published without a person checking it against the publication. The publication itself is the authors' own work — this badge says nothing about it.
From OpenAlex, which stores abstracts as an
index of words and their positions: what is shown is rebuilt from that,
and reads fluently whether or not it is what the author wrote.
Abstract
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.
How it got here
How it got here
agent via openalex
Added
2026-10-24 16:27 UTC
Not denied by
a person 2026-10-29 17:12 UTC
Cite it as
@article{hemaspaandra1996price,
title = {The Price of Universality},
author = {Edith Hemaspaandra},
year = {1996},
journal = {Notre Dame Journal of Formal Logic},
publisher = {Duke University Press},
volume = {37},
number = {2},
pages = {174--203},
doi = {10.1305/ndjfl/1040046086},
}