Gewichtete Automaten und gewichtete Logiken für diskrete Strukturen
Final Report Abstract
In der Theoretischen Informatik sind endliche Automaten und Beschreibungen ihres Verhaltens durch rationale Ausdrücke oder Formeln der Logik von Kleene, Büchi und Elgot fundamental. Darauf aufbauend, untersuchten eine Reihe von Forschergruppen das Verhalten endlicher Automaten auch auf anderen Strukturen wie Bäumen, Bildern oder Graphen und leiteten äquivalente Beschreibungen durch rationale Ausdrücke oder Logiken her. Gewichtete Automaten sind ein quantitatives Modell derartiger Automaten. Sie erweitern endliche Automaten, indem sie zusätzlich mögliche Kosten, Zeitdauer, Verbrauch von Ressourcen oder die Wahrscheinlichkeit des Erfolgs von Transitionen berücksichtigen. Sie ermöglichen damit quantitative Aussagen über Prozessabläufe von diskreten Systemen, welche durch diskrete Strukturen wie Wörter, Bäume, Bilder, Graphen beschrieben werden. Für die Berechnung der Gesamtkosten der Prozessabläufe gibt es, motiviert durch verschiedene Anwendungen, eine Reihe von Möglichkeiten, z. B. die Summe der Kosten, den Maximal- oder Minimalverbrauch von Ressourcen, oder aktuell die Ermittlung von Durchschnittswerten. Ziel des Projektes war, aufbauend auf eine kürzlich entwickelte gewichtete Logik, die Untersuchung von derartigen aktuellen, neuartigen quantitativen Automaten und ihrer Verbindungen zu quantitativen Logiken mit Mitteln der gewichteten Automaten. Es wurde gezeigt, dass sich z. B. die Durchschnittsberechnungen des Verbrauchs von Ressourcen mit diesen Methoden, die für gewichtete Automaten enwickelt wurden, analysieren und mit geeigneten quantitativen Logiken äquivalent beschreiben lassen. Derartige Äquivalenzresultate wurden auch für andere Strukturen, wie Bäume mit und ohne Rang, geschachtelte Wörter, Graphen, für kompliziertere Automatenmodelle wie Realzeit-Kellerautomaten, Registerautomaten für Datenwörter und probabilistische Automaten sowie für diverse Kostenarten, z. B. auch mehrwertige Kosten, und ihre Berechnungen entwickelt. Ferner wurden gewichtete Netzwerke, Zerlegungen von gewichteten Transitionssystemen, gewichtete lineare dynamische Logik, Axiomatiken für das Verhalten quantitativer Automaten sowie quantitative kontextfreie Sprachen untersucht. Die Resultate führten zu drei erfolgreichen Dissertationen und erhielten einen Best Paper Award.
Publications
- Weighted automata and regular expressions over valuation monoids. International Journal of Foundations of Computer Science, 22(8):1829–1844, 2011
M. Droste and I. Meinecke
(See online at https://doi.org/10.1142/S0129054111009069) - Coverings and decompositions of semiring-weighted finite transition systems. In J. Ahsan, J. N. Mordeson, and M. Shabir, editors, Fuzzy Semirings with Applications to Automata Theory, chapter 11 (invited), pages 193–216. Springer, 2012
M. Droste, I. Meinecke, B. Šešelja, and A. Tepavcevic
(See online at https://doi.org/10.1007/978-3-642-27641-5_11) - Probabilistic automata and probabilistic logic. In Mathematical Foundations of Computer Science (MFCS), volume 7464 of LNCS, pages 813–824. Springer, 2012
T. Weidner
(See online at https://doi.org/10.1007/978-3-642-32589-2_70) - Weighted automata and weighted MSO logics for average and long-time behaviors. Information and Computation, 220:44–59, 2012
M. Droste and I. Meinecke
(See online at https://doi.org/10.1016/j.ic.2012.10.001) - Parameterized model checking of weighted networks. Theoretical Computer Science, 534:69–85, 2014
I. Meinecke and K. Quaas
(See online at https://doi.org/10.1016/j.tcs.2014.02.037) - Logics for weighted timed pushdown automata. In Fields of Logic and Computation II, volume 9300 of LNCS, pages 153–173. Springer, 2015
M. Droste and V. Perevoshchikov
(See online at https://doi.org/10.1007/978-3-319-23534-9_9) - Weighted automata and logics on graphs. In Mathematical Foundations of Computer Science (MFCS), Part I, volume 9234 of LNCS, pages 192–204. Springer, 2015
M. Droste and S. Dück
(See online at https://doi.org/10.1007/978-3-662-48057-1_15) - Multi-weighted automata and MSO logic. Theory of Computing Systems, 59(2):231–261, 2016
M. Droste and V. Perevoshchikov
(See online at https://doi.org/10.1007/s00224-015-9658-9) - Weighted register automata and weighted logic on data words. In International Colloquium on Theoretical Aspects of Computing (ICTAC), volume 9965 of LNCS, pages 370–384, 2016
P. Babari, M. Droste, and V. Perevoshchikov
(See online at https://doi.org/10.1007/978-3-319-46750-4_21) - Weighted automata and logics for infinite nested words. Information and Computation, 253:448–466, 2017
M. Droste and S. Dück
(See online at https://doi.org/10.1016/j.ic.2016.06.010)
