Komplexität modaler Logiken

Schneider, Thomas GND

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.

Cite

Citation style:

Schneider, Thomas: Komplexität modaler Logiken. Jena 2002.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

open graphic

Rights

Use and reproduction:
All rights reserved

Export