Gewichtete Automaten und gewichtete Logiken für diskrete Strukturen

点击翻译按钮获取中文摘要

Ziel des Projektes ist die Untersuchung von gewichteten Automatenmodellen und geeigneten gewichteten Logiken für eine Reihe von verschiedenen diskreten Strukturen. Klassische Resultate von Kleene und Büchi beschreiben das Verhalten von endlichen Automaten auf Wörtern durch rationale Ausdrücke und mit Hilfe von Formeln der Logik. In der Informatik wurde in den letzten Jahren von einer Reihe von Forschergruppen das Verhalten endlicher Automaten auch auf anderen Strukturen wie teilweisen Ordnungen, Bildern oder Graphen intensiv untersucht und äquivalente Beschreibungen durch rationale Ausdrücke oder Logiken hergeleitet. Gewichtete Automaten berücksichtigen zusätzlich mögliche Kosten, Zeitdauer, Verbrauch von Ressourcen oder die Wahrscheinlichkeit des Erfolgs von Transitionen; sie ermöglichen damit quantitative Aussagen über das Verhalten von Automaten. Im beantragten Projekt sollen geeignete Modelle von gewichteten Automaten auf endlichen und unendlichen Wörtern, Bäumen, verteilten Strukturen, Bildern und Graphen untersucht werden. Ziele sind unterschiedliche Beschreibungen ihres quantitativen Verhaltens sowie Charakterisierungen mit Hilfe von Verfeinerungen einer kürzlich entwickelten gewichteten Logik