Informatik, TU Wien

Zur Ausdrucksstärke verschiedener Logiken über ungeordneten Bäumen

In der Informatik und Linguistik wird unter Bäumen meist geordnete Bäume verstanden.

In der Informatik und Linguistik wird unter Bäumen meist geordnete Bäume verstanden. In geordneten Bäumen gibt es für jeden Knoten eine lineare Ordnung auf den Töchterknoten. Bei ungeordneten Bäumen ist dies bei keinem Knoten der Fall. Ungeordnete Bäume bilden das sog. Datenbankmodell von XML. In der Linguistik spielen sie als Modell von Dependenzgrammatiken eine Rolle. Im Vortrag werden wir eine Reihe von Logiken aus den Bereichen Logiken zweiter Stufe, Fixpunktlogiken und Automatenlogiken in ihrer relativen Ausdrucksstärke auf ungeordneten Bäumen miteinander vergleichen. Es ergibt sich ein Bild, das sehr viel komplexer und interessanter ist als im Falle geordneter Bäume.