FI:DBLOK5 Weighted Finite Automata - Course Information
DBLOK5 Weighted Finite Automata
Faculty of InformaticsAutumn 2014
- Extent and Intensity
- 2/0. 1 credit(s) (plus extra credits for completion). Type of Completion: k (colloquium).
- Teacher(s)
- Werner Kuich (lecturer), prof. RNDr. Antonín Kučera, Ph.D. (deputy)
- Guaranteed by
- prof. RNDr. Antonín Kučera, Ph.D.
Faculty of Informatics
Supplier department: Faculty of Informatics - Timetable
- Thu 23. 10. 14:00–15:50 B517, Fri 24. 10. 12:00–13:50 B410, Thu 20. 11. 14:00–15:50 B517, Fri 21. 11. 12:00–13:50 B410, Thu 11. 12. 14:00–15:50 B517, Fri 12. 12. 12:00–13:50 B410
- Prerequisites
- The lecture is selfcontained, i.e., it contains all definitions and results needed. The handling of finite automata is mathematically oriented (especially the proofs) and so mathematical maturity is needed. Knowledge of classical automata theory concerning finite automata is helpful.
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- there are 8 fields of study the course is directly associated with, display
- Syllabus
- Introduction into semiring theory, especially into the theory of Conway semirings; a Kleene Theorem on weighted finite automata over Conway semirings; the complexity of computing the star of a matrix and the all-pairs shortest distance problem for directed graphs. Conway semiring-semimodule pairs and quemirings; weighted Büchi automata (infinite words) over quemirings and a Kleene Theorem.
- Literature
- Zoltan Esik, Werner Kuich: Modern Automata Theory, Chapter 1, Chapter 5, Sections 5.1 – 5.4. This electronic book can be downloaded from dmg.tuwien.ac.at/kuich.
- Language of instruction
- English
- Further Comments
- The course is taught only once.
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/fi/autumn2014/DBLOK5