- Stephan Kepser, Seminar für Sprachwissenschaft, Universität Tübingen, zum Thema Zur Berechenbarkeit und Komplexität von RSRL. Ort: Komplex Golm, Haus 24, R.075. Zeit: Dienstag, 15. Januar '02, 17 Uhr s.t.
Abstract
Wir stellen ein Berechenbarkeits- und ein Komplexitätsresultat für die
Relational Speciate Reentrant Logic (RSRL) vor. RSRL ist eine
Beschreibungslogik, die zur Formalisierung der Head-Driven Phrase
Structure Grammar entworfen wurde. Wir zeigen, daß - gegeben eine
RSRL-Formel und eine endliche Interpretation - es im allgemeinen
nicht entscheidbar ist, ob die Formel in der Interpretation wahr ist
oder nicht, und zwar durch Rückführung auf
Post-Korrespondenz-Probleme. Für sogenannte kettenlose RSRL, eine
semantisch schwächere Variante, in der die Ausdruckstärke der Logik
deutlich eingeschränkt ist, zeigen wir, wenn eine Klasse von
Strukturen in kettenloser RSRL definierbar ist, dann ist sie
entscheidbar durch eine Turingmaschine, die PTIME-beschränkt ist in
der Größe der Eingabestrukturen.