Komplexität modaler Logiken

Schneider, Thomas

In dieser Arbeit wird das Erfüllbarkeitsproblem von Systemen der modalen Aussagenlogik komplexitätstheoretisch untersucht. Um dies vorzubereiten, wird auf die erforderlichen Aspekte der Theorie modaler Logiken eingegangen und eine Hierarchie wichtiger normaler modaler Systeme anhand semantischer Gesichtspunkte aufgestellt. Das Hauptaugenmerk der komplexit¨atstheoretischen Betrachtungen richtet sich auf normale unimodale Logiken, die für die Klasse NP vollständig sind. Neben aus der Literatur bekannten Resultaten wird die NP-Vollständigkeit der Systeme D4E, K4B und K4E gezeigt. Außerdem wird ein Überblick über bisher bekannte PSPACE-Vollständigkeitsergebnisse gegeben. Vermutet wird die NP-Vollständigkeit der Logiken K4.2 und S4.2 sowie die PSPACE-Vollständigkeit von KE, KB, DE, DB, B. Eine weitere offene Frage ist die nach einer einheitlichen Reduzierbarkeit zwischen modalen Systemen, die ineinander enthalten sind.

Zitieren

Zitierform:

Schneider, Thomas: Komplexität modaler Logiken. 2006.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export