Gewichtete Baumautomaten über Multioperator-Monoiden
Final Report Abstract
Bäume, das Erkennen ihrer strukturellen Eigenschaften und ihre Transformationen sind in der Informatik wichtige Konzepte bzw. Aufgaben. Mögliche formale algorithmische Werkzeuge für diese Erkennungs- und Transformationsvorgänge sind Baumautomaten bzw. Baumübersetzer. In der Theorie der Automaten und formalen Sprachen wurden Baumautomaten und Baumübersetzer seit den 60er Jahren des vergangenen Jahrhunderts intensiv studiert. In machen Bereichen, wie z.B. der Verarbeitung natürlicher Sprache (natural language processing, NLP), ist man nicht nur an strukturellen oder qualitativen Aspekten sondern auch an quantitativen Aspekten interessiert; beispielsweise modelliert man im statistischen NLP die Mehrdeutigkeit natürlicher Sprachen dadurch, daß jedem möglichen Strukturbaum eines Wortes eine Wahrscheinlichkeit zuordnet wird; NLP-Algorithmen rechnen dann mit diesen Wahrscheinlichkeiten. Die formalen Grundlagen dieser probabilistischen oder, allgemeiner: Semiring-gewichteten Baumautomaten und Baumübersetzer wurden seit den 80er Jahren des vergangenen Jahrhunderts erarbeitet. Allerdings lassen sich manche einfachen, quantitativen Erkennungs- oder Transformationsvorgänge nur unangemessen kompliziert durch Semiring-gewichtete Baumautomaten beschreiben, weil die Art der Gewichtsauswertung (durch die binäre Multiplikation des Semirings) nicht zum Aufbau der Bäume mit beliebig-stelligen Symbolen passt. Deshalb war die Zielsetzung dieses Projektes, gewichtete Baumautomaten/-übersetzer über flexibleren, ausdrucksstärkeren algebraischen Strukturen zu studieren. Hierzu wählten wir die Multioperator-Monoide (kurz: M-Monoide). Ein M-Monoid (A, +, 0, Ω) besteht aus einem kommutativen Monoid (A, +, 0) und einer Menge Ω von Operationen auf A. Sei M ein Baumautomat; jeder Transition von M an einem k-stelligen Eingabesymbol wird nun eine k-stellige Operation aus Ω zugewiesen; das Gewicht eines Laufes über einem Eingabebaum t erhält man durch Ausrechnen der Operationen, die im Lauf kodiert sind. Schließlich ordnet die Baumreihe LM : TΣ → A einem Eingabebaum t die Summe (vermöge +) der Gewichte aller Läufe auf t zu. Wir nennen diese Baumautomaten M-gewichtet. Im Rahmen dieses Projektes haben wir für M-gewichtete Baumautomaten grundlegende automatentheoretische Fragestellungen geklärt, wie z.B. Determinisierung, Dekomposition, Kleenes Theorem und Büchi’s Theorem. In einem zweiten Schwerpunkt, haben wir weighted monadic datalog transducer als Spezifikations- und Analysewerkzeug für gewichtete XML-Anfragen definiert und dafür einerseits automatentheoretische Fragenstellungen betrachtet (wie Vergleiche der Ausdruckssärke) und auch algorithmische Fragestellungen (wie Komplexität der Interpretation auf einem Eingabebaum). Insgesamt zeigte sich, daß die Gewichtung mit M-Monoiden besser zu Baumautomaten paßt als die Gewichtung mit Semiringen und daß erstgenannte sehr robust ist. Die in einer Arbeit des Projekts entwickelte gewichtete Logik für M-gewichtete Baumautomaten erscheint interessant, weil • sie auf ganz natürliche Weise der Arbeit der Baumautomaten entsprach und • sie die gewichtete Logik für Semiring-gewichtete Baumautomaten subsumiert. Wir möchten diese gewichtete Logik weiter ausbauen.
Publications
- Learning Deterministically Recognizable Tree Series. J. Automata, Languages and Combinatorics, 12, 333-354, 2007
F. Drewes and H. Vogler
- Weighted monadic datalog. Theoretical Computer Science, 403 (2008), pages 221-238
T. Stüber and H. Vogler
- A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids. Theory of Computing Systems 44(3), 455-499, 2009
Z. Fülöp, A. Maletti, and H. Vogler
- Decomposition of Weighted Multioperator Tree Automata. Int. J. Foundations of Computer Sci., 20(2):221-245, 2009
T. Stüber, H. Vogler, and Z. Fülöp
- Monadic datalog tree transducers, eds. A.H. Dediu, A.M. Ionescu, C. Martin-Vide: LATA 2009, LNCS 5457, pp. 267-278, Springer-Verlag, 2009
M. Büchse and T. Stüber
- Weighted monadic datalog tree transducers. 2010
D. Geisler and T. Stüber
