Transducers 1000-2M23PA
1. Mealy machines and the Krohn-Rhodes Theorem
2. Rational string-to-string functions
3. Weighted automata, mainly over fields
4. Polynomial automata and the Hilbert method
5. Linear regular functions, including: two-way transducers, monadic second-order logic, register transducers, combinators and Krohn-Rhodes decompositions
6. Polynomial regular functions, including: pebble transducers, Monadic second-order logic, for programs, the λ-calculus
7. Deciding f=g, i.e. the equivalence problem
8. Tree transducers
9. Graph transducers
Main fields of studies for MISMaP
mathematics
Type of course
Mode
Prerequisites
Course coordinators
Bibliography
The basic material will be interactive slides prepared during the course.
Supplementary literature:
1. Bojańczyk, Czerwiński “Automata Toolbox”
2. Sakharovitch “Elements of Automata Theory”
Notes
|
Term 2023L:
None |
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: