DBLOK5 Weighted Finite Automata

Faculty of Informatics
Autumn 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