This is the page for a transducer course, given at the University of Warsaw in 2024.
The tutorials are by Aliaume Lopez, you can find the problems here.
Your final grade will be a combination of: (1) an oral exam at the end of the semester; (2) homeworks.
Lectures
Mealy machines
Slides
- Definition of Mealy machines
- Closure under composition
- The Krohn-Rhodes theorem
Rational functions
Slides
- Unambiguous nondeterministic automata with output
- Eilenberg Bi-machines
- Their equivalence
- A Krohn-Rhodes decomposition
- Deciding equivalence
Enter logic
Slides
- MSO = regular languages
- MSO relabelings = letter-to-letter rational
- the first-order fragment of MSO
Two-way automata
Slides
- Two-way automata with output
- Closure under pre-composition
- Decidable equivalence
MSO transductions
Slides
- Definition of MSO transductions
- Equivalence with previous two models
Streaming stream transducers
Slides
- Definition of copy less streaming stream transducers
- Equivalence with two-way automata with output
- The copyful version, and decidability of equivalence for it
List functions
Slides
- Definition of the linear list functions
- Their first-order fragment
- Proof that they define the same functions as two-way transducers
Introduction to polyregular functions
Slides
- Polynomial Krohn-Rhodes primes
- Polynomial list functions
- For transducers
- Equivalence of all three models
Pebble transducers
Slides
- Pebble transducers
- Their equivalence to the polynomial list functions and for transducers
A functional programming language
- Polynomial list functions with λ
Polynomial interpretations
- String-to-string MSO interpretations
- Proof that they define exactly the polyregular functions