AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete
Félix Bou, Marco Cerami, Francesc Esteva

Last modified: 2011-06-28

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.

Full Text: PDF