Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete

Bou, Félix; Cerami, Marco; Esteva, Francesc

doi:10.5591/978-1-57735-516-8/IJCAI11-136

Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete

Félix Bou, Marco Cerami, Francesc Esteva

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 774-778.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-136

Abstract

It is well-known that satisfiability (and hence validity) in the minimal classical modal logic is a PSPACE-complete problem. In this paper we consider the satisfiability and validity problems (here they are not dual, although mutually reducible) for the minimal modal logic over a finite Lukasiewicz chain, and show that they also are PSPACE-complete. This result is also true when adding either the Delta operator or truth constants in the language, i.e. in all these cases it is PSPACE-complete.

Félix Bou, Marco Cerami, and Francesc Esteva. 2011. Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 774–778. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-136

@inproceedings{ijcai2011p136,
  title     = {Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete},
  author    = {Bou, Félix and Cerami, Marco and Esteva, Francesc},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {774--778},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-136},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-136},
}

TY  - CPAPER
TI  - Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete
AU  - Bou, Félix
AU  - Cerami, Marco
AU  - Esteva, Francesc
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 774
EP  - 778
DO  - 10.5591/978-1-57735-516-8/IJCAI11-136
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-136
ER  -