https://www.dagstuhl.de/23202

14. – 17. Mai 2023, Dagstuhl-Seminar 23202

Regular Transformations

Organisatoren

Rajeev Alur (University of Pennsylvania – Philadelphia, US)
Mikolaj Bojanczyk (University of Warsaw, PL)
Emmanuel Filiot (UL – Brussels, BE)
Anca Muscholl (University of Bordeaux, FR)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Susanne Bach-Bernhard zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

Motivation

Transducers, i.e., automata that output values other than just “yes” or “no”, are one of the oldest computational models in theoretical computer science. They even predate the usual automata, with Rabin and Scott arguing in their 1959 paper that they are better off by “doing away with a complicat-ed output function and having our machines simply give ‘yes’ or ‘no’ answers.” Despite this impres-sive pedigree, transducers have remained an active research topic ever since. Also, connections to practical applications in efficient processing of streaming data have been established recently. The purpose of this Dagstuhl Seminar is to gather researchers working on these topics to discuss recent developments.

We plan to discuss and advance on the following non-exhaustive list of topics during the seminar:

  • regular and polyregular functions: the class of regular string-to-string functions has now gained a central position in the theory of transducers, as witnessed by many recent developments. The semi-nar will discuss those developments as well as classes of functions beyond regular functions, and in particular models of functions of polynomial growth, which have received a lot of attention in the last years.
  • equivalence problems: transducer equivalence is one of the most central algorithmic problems in transducer theory. Algebraic techniques have been used recently to tackle this problem but important questions remain, such as whether or not the equivalence problem is decidable for polyregular functions.
  • with finite model theory: the last decade has seen an explosion of new work on the theory of graph classes where first-order model checking is tractable (first-order model checking is not tractable on the class of all graphs). A recent trend in this work has been to use transducers, by considering images of simple graphs under certain transducers, or by considering classes that cannot yield all graphs by applying certain transducers.
  • semantics: origin semantics means tagging the output by the positions of the input that generated that output. Origin semantics has shed new lights on algebraic characterizations of regu-lar functions and equivalence problems for transducers.
  • membership problems: unlike deterministic finite automata, transducers are not robust under natural extensions such as non-determinism, bidirectionality, pebbles, … This induces classes of functions of various expressive power. Class membership problems, which ask to decide whether a function given as a transducer in some class belongs to some other class, have seen important de-velopments in the last few years.

Motivation text license
  Creative Commons BY 4.0
  Rajeev Alur, Mikolaj Bojanczyk, Emmanuel Filiot, and Anca Muscholl

Dagstuhl-Seminar Series

Classification

  • Databases
  • Formal Languages And Automata Theory
  • Logic In Computer Science

Keywords

  • Transducers
  • Automata with outputs
  • Transformations

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.