Computational complexity of multimodal logics based on rough sets

• Autorzy: Demri, S. , Stepaniuk, J.
• Języki publikacji: EN

Abstrakty

EN

We characterize the computational complexity of a family of approximation multimodal logics in which interdependent modal connectives are part of the language. Those logics have been designed to reason in presence of incomplete information in the sense of rough set theory. More precisely, we show that all the logics have a PSPACE-complete satisfiability problem and we define a family of tolerance approximation multimodal logics whose satisfiability is EXPTIME-complete. This illustrates that the PSPACE upper bound for this kind of multimodal logics is a very special feature of such logics. The PSPACE upper bounds are established by adequately designing Ladner-style tableaux-based procedures whereas the EXPTIME lower bound is established by reduction from the global satisfiability problem for the standard modal logic B.

Słowa kluczowe

EN

rough sets; tolerance rough sets; multimodal logic; computational complexity; Ladner-style algorithm

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2000
• Tom: Vol. 44, Nr 4
• Strony: 373-396
• Opis fizyczny: bibliogr. 32 poz.

Twórcy

autor

Demri, S.

autor

Stepaniuk, J.

• Lab.Spécification et Vérification, ENS de Cachan and CNRS UMR 8643, 61 Av.Pdt. Wilson, 94235 Cachan Cedex, France,