|
| volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 1 van 4 gevonden artikelen
| Titel: |
Computational Complexity of Multimodal Logics \newline Based on Rough Sets |
| Auteur: |
Stéphane Demri Jarosław Stepaniuk |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 44 (2003) nr. 4 pagina's 373-396 |
| Jaar: |
2003-07-11 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 1 van 4 gevonden artikelen
| volgende >> |