Automata, matrices, codes 1000-2M25AMK
1. Introduction, weighted automata as a generalisation of finite automata, or a generalisation of linear recurrence systems. Different semirings over which such automata are defined.
2. Schützenberger's theorem on decidability of equivalence over fields.
3. Unambiguous automata and the mortality problem.
4. Undecidability of the mortality problem for integer matrices.
5. Main definitions from the theory of codes and the relation between regular codes and unambiguous automata.
6. Synchronising codes and the Černý Conjecture.
7. Linear recurrence systems: Skolema-Mahlera-Lecha theorem and NP-hardness of the Skolem problem.
8. Elementary upper bound on the size of finite rational matrix groups. The special case of one-generated rational matrix groups.
9. Polynomial-time algorithm for deciding finiteness of ration matrix groups.
Main fields of studies for MISMaP
mathematics
Type of course
Course coordinators
Learning outcomes
The student can recognise frontiers of decidability for different models. the student can model various problems using different automata models. The student understand mathematical tools in modern automata theory and can apply them.
Assessment criteria
Homework and an exam.
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: