The Complexity of Reasoning with Boolean Modal Logics
From International Center for Computational Logic
The Complexity of Reasoning with Boolean Modal Logics
Carsten LutzCarsten Lutz, Ulrike SattlerUlrike Sattler
Carsten Lutz, Ulrike Sattler
The Complexity of Reasoning with Boolean Modal Logics
In Frank Wolter and Heinrich Wansing and Maarten de Rijke and Michael Zakharyaschev, eds., Advances in Modal Logics Volume 3, 2001. CSLI Publications, Stanford
The Complexity of Reasoning with Boolean Modal Logics
In Frank Wolter and Heinrich Wansing and Maarten de Rijke and Michael Zakharyaschev, eds., Advances in Modal Logics Volume 3, 2001. CSLI Publications, Stanford
- KurzfassungAbstract
In this paper, we investigate the complexity of reasoning with various Boolean Modal Logics. The main results are that (i) adding negation of modal parameters to (multi-modal) K makes reasoning ExpTime-complete and (ii) adding atomic negation and conjunction to K even yields a NExpTime-complete logic. The last result is relativized by the fact that it depends on an infinite number of modal parameters to be available. If the number of modal parameters is bounded, full Boolean Modal Logic becomes ExpTime-complete. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ LutzSattler-AiML-01,
author = {C. {Lutz} and U. {Sattler}},
booktitle = {Advances in Modal Logics Volume 3},
editor = {Frank {Wolter} and Heinrich {Wansing} and Maarten de {Rijke} and Michael {Zakharyaschev}},
publisher = {CSLI Publications, Stanford},
title = {The Complexity of Reasoning with Boolean Modal Logics},
year = {2001},
}
