ML Anthology

Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete

Félix Bou, Marco Cerami, Francesc Esteva
IJCAI 2011 pp. 774-779
doi:10.5591/978-1-57735-516-8/IJCAI11-136 /ijcai/2011/bou2011ijcai-finite/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Bou et al. "Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-136

Markdown

[Bou et al. "Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/bou2011ijcai-finite/) doi:10.5591/978-1-57735-516-8/IJCAI11-136

BibTeX

@inproceedings{bou2011ijcai-finite,
  title     = {{Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete}},
  author    = {Bou, Félix and Cerami, Marco and Esteva, Francesc},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {774-779},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-136},
  url       = {https://mlanthology.org/ijcai/2011/bou2011ijcai-finite/}
}