Weighted automata 1000-2M22AW
1. Introduction, weighted automata as a generalisation of finite automata or as a generalisation of linear recursive sequences. Several semirings for which such automata are defined.
2. Schützenberger’s theorem about decidability of equivalence over fields. Learning weighted automata.
3. Probabilistic automata
4. Subclasses defined according to the number of runs in the automaton. Weber and Seidl characterisation.
5. Linear recursive sequences: Skolem-Mahler-Lech theorem and NP-hardness of the Skolem problem.
6. Undecidability of most of the problems for weighted automata.
7. Hashiguchi’s theorem on decidability of the boundedness problem over the min-plus semiring.
8. Decidability of the finiteness problem with elementary bounds.
9. The determinisation problem, decidability for unambiguous automata.
10. Nonlinear weighted automata.
Main fields of studies for MISMaP
Type of course
Requirements
Prerequisites
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: