Synthesis of transducers from automaton definable specifications

• Applicant: Privatdozent Dr. Christof Löding
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 287809235

• Final Report Year: 2021

Final Report Abstract

Bei dem Projekt handelt es sich um Grundlagenforschung in der theoretischen Informatik. Aus einer Beschreibung für das Ein-Ausgabeverhalten eines Systems soll automatisch ein System konstruiert werden, das aus den möglichen Ein-Ausgabeverhalten der Beschreibung ein mögliches umsetzt. Als Formalismus für die Beschreibungen und Systeme wurden in dem Projekt dabei endliche Automaten, also eine einfache Form von Programmen, verwendet. In dem Projekt wurden Algorithmen zur Lösung dieses Syntheseproblems für neue Klassen von Automaten entwickelt. Ein Großteil der formulierten Ziele wurden dabei erreicht. Insbesondere wurde eine umfassende Theorie der Synthese von sequentiellen Transducern aus Teilklassen von rationalen Relationen entwickelt. Bei der Synthese von Baumtransducern wurden einige Algorithmen für einfache Klassen von Automaten entwickelt, aber es hat sich auch herausgestellt, dass man sehr schnell in den Bereich der algorithmisch nicht mehr lösbaren Probleme kommt. Wir haben damit den aktuellen Forschungsstand zu diesem Gebiet der theoretischen Informatik um einige Ergebnisse erweitert und zu dem besseren Verständnis der im Projekt untersuchten Modelle beigetragen.

Publications

• Synthesis from Weighted Specifications with Partial Domains over Finite Words. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, 46:1-46:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2020
  Emmanuel Filiot, Christof Löding, Sarah Winter
  (See online at https://doi.org/10.4230/LIPIcs.FSTTCS.2020.46)
• On equivalence and uniformisation problems for finite transducers. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 125:1–125:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016
  Emmanuel Filiot, Ismaël Jecker, Christof Löding, Sarah Winter
  (See online at https://doi.org/10.4230/LIPIcs.ICALP.2016.125)
• Uniformization problems for tree-automatic relations and top-down tree transducers. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26 2016 - Kraków, Poland, volume 58 of LIPIcs, pages 65:1-14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016
  Löding, Christof and Winter, Sarah
  (See online at https://doi.org/10.4230/LIPIcs.MFCS.2016.65)
• Synthesis of transducers from relations on finite words and trees. Dissertation. RWTH Aachen University, Germany, 2018
  Sarah Winter
  (See online at https://dx.doi.org/10.18154/RWTH-2019-04126)
• Uniformization Problems for Synchronizations of Automatic Relations on Words. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. 142:1-142:13. 2018
  Sarah Winter
  (See online at https://doi.org/10.4230/LIPIcs.ICALP.2018.142)
• Resynchronized Uniformization and Definability Problems for Rational Relations. CoRR abs/2104.12508 (2021)
  Christof Löding, Sarah Winter