Gewichtete Baumautomaten über Multioperator-Monoiden

• Applicant: Professor Dr.-Ing. Heiko Vogler
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 28443503

Quantitative (oder: gewichtete) Automatenmodelle gehen über die üblichen endlichen Automaten hinaus, indem zusätzlich mögliche Kosten, Zeitdauer, Verbrauch von Ressourcen oder die Wahrscheinlichkeit des Erfolgs von Transitionen modelliert werden können. Sie ermöglichen damit quantitative Aussagen über Prozessabläufe eines diskreten Systems, welches durch diskrete Strukturen wie Wörter, Bäume, teilweise Ordnungen, Graphen beschrieben wird. Sie haben aktuelle Anwendungen beispielsweise in der digitalen Bildverarbeitung [ CK93, Haf99, Kat01, Era02], der natürlichen Spracherkennung [Moh97, MPR00, BGW00] und der kombinatorischen Optimierung in Netzwerken [BH00, BCOQ92, OSG98]. Dieses quantitative Automatenmodell für diskrete Strukturen und wesentliche Erweiterungen sollen in beiden einzelnen Forschungsprojekten entwickelt und untersucht werden. In der Grundversion besteht jeder gewichtete endliche Automat (weighted nite automaton-WFA) aus einem endlichen Automaten, d.h. (Transitions-)Graphen, in dem die Knoten die möglichen Situationen oder Zustände des zu Grunde liegenden Systems und die Kanten die möglichen Transitionen beschreiben. Die Kanten sind jeweils mit der sie verursachenden Aktion und einem Gewicht (beispielsweise einer reellen Zahl) beschriftet. Die Gewichte können etwa die Zeitdauer der Ausführung, die Wahrscheinlichkeit des Erfolgs, oder den entstehenden Gewinn oder die verursachten Kosten (Verbrauch von Ressourcen) der Transition bedeuten. Ein Pfad, d.h. eine Folge von Transitionen, stellt eine mögliche Realisierung eines Prozesses des Systems dar. Ein Prozess, d.h. eine Folge von Aktionen (ein Wort), kann dabei i.a. durch verschiedene Pfade realisiert werden; der Automat ist also grundsätzlich nichtdeterministisch. Jeder Pfad hat ein Gesamtgewicht (etwa die Summe der Gewichte der einzelnen Transitionen), und jeder Aktionsfolge kann man z.B. das minimale Gewicht aller seiner Pfadrealisierungen zuordnen. Das Verhalten des Systems wird dann durch diese Zuordnung von Gewichten zu jeder erfolgreichen Aktionsfolge beschrieben... Ziel der gemeinsamen Forschung ist die Untersuchung und Erweiterung dieses Modells von gewichteten Automaten.

• DFG Programme: Research Grants