Gewichtete Automaten und gewichtete Logiken für diskrete Strukturen

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

• Final Report Year: 2020

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
  DROSTE, MANFRED & MEINECKE, INGMAR
  
• 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
  Droste, Manfred; Meinecke, Ingmar; Šešelja, Branimir & Tepavčević, Andreja
  
• Probabilistic automata and probabilistic logic. In Mathematical Foundations of Computer Science (MFCS), volume 7464 of LNCS, pages 813–824. Springer, 2012
  Weidner, Thomas
  
• Weighted automata and weighted MSO logics for average and long-time behaviors. Information and Computation, 220:44–59, 2012
  Droste, Manfred & Meinecke, Ingmar
  
• Parameterized model checking of weighted networks. Theoretical Computer Science, 534:69–85, 2014
  Meinecke, Ingmar & Quaas, Karin
  
• Logics for weighted timed pushdown automata. In Fields of Logic and Computation II, volume 9300 of LNCS, pages 153–173. Springer, 2015
  Droste, Manfred & Perevoshchikov, Vitaly
  
• Multi-weighted automata and MSO logic. Theory of Computing Systems, 59(2):231–261, 2016
  Droste, Manfred & Perevoshchikov, Vitaly
  
• Weighted automata and logics on graphs. In Mathematical Foundations of Computer Science (MFCS), Part I, volume 9234 of LNCS, pages 192–204. Springer, 2015
  Droste, Manfred & Dück, Stefan
  
• 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
  Babari, Parvaneh; Droste, Manfred & Perevoshchikov, Vitaly
  
• Weighted automata and logics for infinite nested words. Information and Computation, 253:448–466, 2017
  Droste, Manfred & Dück, Stefan