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

Polyregular functions 1

Slides

• Polynomial Krohn-Rhodes primes
• Polynomial list functions
• For transducers

Polyregular functions 2

• Pebble transducers
• λ-calculus

Polynomial interpretations

• String-to-string MSO interpretations
• Proof that they define exactly the polyregular functions