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.