Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 23202

Regular Transformations

( 14. May – 17. May, 2023 )

(zum Vergrößern in der Bildmitte klicken)

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:



Gemeinsame Dokumente



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.
Copyright Rajeev Alur, Mikolaj Bojanczyk, Emmanuel Filiot, and Anca Muscholl


Verwandte Seminare
  • Dagstuhl-Seminar 13192: Tree Transducers and Formal Methods (2013-05-05 - 2013-05-08) (Details)
  • Dagstuhl-Seminar 17142: Formal Methods of Transformations (2017-04-02 - 2017-04-05) (Details)

  • Databases
  • Formal Languages and Automata Theory
  • Logic in Computer Science

  • transducers
  • automata with outputs
  • transformations