Fachbereich Informatik - Aktuell

21.01.2019

Disputation Silke Czarnetzki

am Mittwoch, 30. Januar 2019, um 15:00 Uhr in Raum A104, Sand 1


Silke Czarnetzki


Stone-Dualität in der Komplexitätstheorie


Berichterstatter 1: Dr. Andreas Krebs
Berichterstatter 2: Prof. Dr. Klaus-Jörn Lange


Die Verknüpfungen zwischen regulären Sprachklassen, Algebra, Logik und Topologie sind in vielerlei Hinsicht bereits erschlossenes Land: Das Blockprodukt verknüpft endliche Monoide mit der Struktur logischer Formeln, die Struktur logischer Formeln lässt sich durch Transduktoren auf reguläre Sprachklassen abbilden, reguläre Sprachklassen wiederum werden von endlichen Monoiden erkannt, deren projektiver Limes ein topologischer Raum ist, und dieser topologische Raum ist eindeutig durch eine reguläre Sprachklasse bestimmt. Dies alles beschreibt nur einen gröbsten Auszug der bekannten Beziehungen.
Wagen wir uns außerhalb des Gebietes der regulären Sprachen, sind besonders die Beziehungen zwischen Topologie und Algebra weitläufig unbekanntes Land und Teil aktueller Forschungen, deren Herzstück die bereits 1936 von Stone bewiesene Dualität zwischen Bool‘schen Algebren und topologischen Räumen (sog. Stone Räumen) bildet. Tatsächlich fußt auch die Beziehung zwischen regulären Sprachklassen und Topologie auf dieser Dualität, so dass sie eine nahtlose Erweiterung der bereits bekannten Beziehungen auf nicht reguläre Sprachklassen ermöglichen könnte.
Genau hier setzt das Thema der Dissertation an: Die Beziehungen zwischen (nicht regulären) Sprachklassen, Algebra, Logik und Topologie über die von Stone beschriebene Dualität zu erweitern. Im Besonderen wurden die folgenden Themen betrachtet:
• Visibly Pushdown Languages (VPLs): Im Vergleich mit allgemeinen nicht regulären Sprachklassen weisen VPLs eine entscheidende Ähnlichkeit zu den regulären Sprachen auf: Es konnte gezeigt werden, dass sie ebenfalls von endlichen algebraischen Objekten erkannt werden. Diese algebraischen Objekte bilden dann den Schlüssel zur Beschreibung der zu den VPLs assoziierten Stone Räume. Die Endlichkeit spielt hier in der Konstruktion eine tragende Rolle. Insbesondere ergeben sich Beschreibungen von Subklassen durch Gleichungen zwischen Elementen des Stone Raumes der VPLs, die eine algebraische Interpretation zulassen. Konkrete Beispiele wurden für visibly counter Sprachen und die visibly counter Sprachen ohne Höhentest errechnet.
• Durch Logik beschriebene Sprachklassen: Bereits bekannt ist, dass auch das Blockprodukt sich auf adäquate (evt. unendliche) algebraische Objekte erweitern lässt, um die Struktur logischer Formeln widerzuspiegeln, die nicht reguläre Sprachen beschreiben. Diese Objekte wurden leicht verändert, um sie der Betrachtung durch die beschriebene Dualität zugänglicher zu machen und so die Brücke zunächst zwischen Algebra und Topologie zu schlagen. Hierüber gelingt es, nicht ohne technische Kniffe, auch das Blockprodukt auf die Ebene der Topologie zu heben und dort ein Blockprodukt zu definieren, welches die Beziehungen zur Logik widerspiegelt. Offen bleibt bisher eine Beschreibung konkreter größerer Klassen über diese Zusammenhänge.
 

Zurück