https://www.dagstuhl.de/23202

May 14 – 17 , 2023, Dagstuhl Seminar 23202

Regular Transformations

Organizers

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

For support, please contact

Susanne Bach-Bernhard for administrative matters

Michael Gerke for scientific matters

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

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.