Gewichtete Automaten und gewichtete Logiken für diskrete Strukturen

• Applicant: Professor Dr. Manfred Droste
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 28404225

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

• DFG Programme: Research Grants