This is a course on transducers, whose previous edition is here.
Grade. Your grade is the weighted average 2/3 * (grade from oral exam) + 1/3 * (grade from homework). There will be 3 groups of homework problems.
Lecture notes. Here are versions of the lecture notes:
Exam
There are 13 topics for the exam : 1 Mealy, 4 Rational, 6 Regular and 2 Polyregular. These are listed below, together with the section numbers in the notes.
Mealy machines
- (A.1 and A.2) Definition of Mealy machines and the Krohn-Rhodes theorem
Rational functions
- (B.1) Definition of rational relations, and undecidability of their equivalence problem.
- (B.2) Rational functions, their equivalence with bimachines, and the decomposition of rational functions into primes.
- (B.3) Equivalence is decidable for rational functions
- (B.4) Machine independent characterizations of Mealy machines, sequential functions, subsequential functions and rational functions
Regular functions
- (C.1) The prime regular functions and their continuity
- (C.2.1) Continuity of two-way transducers
- (C.2.2) Closure under composition for two-way transducers
- (C.2.3) Decomposition of two-way transducers into primes
- (C.3) SST’s and their equivalence two two-way transducers
- (C.4.3) Regular functions in terms of logic
Polyregular functions
- (D.1) For-transducers and their equialence with prime polyregular functions
- (D.2) Pebble transducers and their equivalence to for-transducers