Multioperator Weighted Monadic Datalog

Abstract

In dieser Arbeit stellen wir ein formales Modell zur Verarbeitung von baumstrukturierten Daten vor. Dieses vereint und generalisiert Konzepte von Baumautomaten, Attributgrammatiken, Monadic Datalog und MSO-Logik. Unser Modell verarbeitet Bäume unter Einsatz von Multioperator-Monoiden und erhält dadurch eine hohe Ausdrucksstärke und vielseitige Einsetzbarkeit. In unserer Arbeit beschreiben und vergleichen wir vier verschiedene Semantiken sowie zahlreiche Normalformen. Einige der Semantiken sind nur dann einsetzbar, wenn das Modell kein zirkuläres Verhalten aufweist; daher entwickeln wir des Weiteren einen Zirkularitätstests. Wir betrachten beispielhaft einige Instanzen unseres Modells und stellen Bezüge zu existierenden Berechnungsmodellen her. Diese Kurzfassung ist eine Zusammenfassung der Kapitel der Dissertation.