The Complexity of Reasoning with Boolean Modal Logics

From International Center for Computational Logic

Toggle side column

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
  • 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},
}