Algebra Seminar talk
2005-12-02
Manfred Droste
Gewichtete Automaten und quantitative Logik
Abstract:
Gewichtete Automaten finden aktuelle Anwendungen zur Beschreibung
von quantitativen Eigenschaften in so verschiedenen Gebieten wie
probabilistische Automaten, digitale Bildverarbeitung oder natürliche
Sprachverarbeitung. Die Gewichte werden auf Grund der vielfältigen
Anwendungsmöglichkeiten allgemein als Elemente eines Semirings
angenommen, wodurch algebraisch auch Burnside-Probleme von
Matrizenmonoiden eine wichtige Rolle spielen.
Büchi und Elgot (1961) charakterisierten in einem klassischen Resultat das Verhalten von ungewichteten Automaten mit Hilfe der Logik, wodurch in der Informatik das Gebiet des Model Checkings entstand.
Wir führen nun eine gewichtete monadische Logik 2. Stufe ein und zeigen, dass sich mit ihren Sätzen genau das quantitative Verhalten von gewichteten Automaten beschreiben lässt. Auf Grund von algebraischen Sätzen zu Burnside-Eigenschaften erhalten wir Konstruktions- und Entscheidbarkeitsresultate.