TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23202

Regular Transformations

( May 14 – May 17, 2023 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23202

Organizers

Contact

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

Related Seminars
  • 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)

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

Keywords
  • transducers
  • automata with outputs
  • transformations