Advanced Theory of Finite Automata
» Diese Veranstaltung wird auf englisch gehalten.
Lecture in summer term 2005
|V2||Mo 14:00 - 15:30 AH I||18.04.2005||Thomas|
|Ü1||Wed 16:00 - 16:45 AH VI||20.04.2005||Thomas, Altenbernd|
This course, given in English, is an introduction to fundamental results about finite automata which extend the basic theory as taught in the undergraduate course on automata theory. An emphasis is given to algorithmic aspects, since the effective implementability of automata theoretic constructions is the main reason why finite automata are an indispensible tool in software science (modelling, design, and verification of systems).
The course has three parts:
- Minimization problems and algebraic methods;
- Automata and logic;
- Automata over trees (like XML-documents).
Most of the relevant material for this course is found in Chapters 1-3 of the course notes for Applied Automata Theory (July 2003) which is available for download.
Combination with other courses
This course can be combined with the course Unendliche Transitionssysteme to a full four hour course (V4, Ü2). In this combination, the material presented will roughly cover the contents of the course Applied Automata Theory from the summer term 2004.
Note: The two courses are strictly independent, each with their own distinct requirements for obtaining a certificate ("Übungsschein"). Obtaining a small certificate (V2, Ü1) requires meeting the criteria for the corresponding course. You can obtain a regular certificate (V4, Ü2) in exchange for the two small certificates.
The course is intended for students in their fifth semester. Basic knowledge of automata theory as presented in basic courses is required for participation.
To obtain a small certificate (V2, Ü1) or the credit points for this course, students have to meet the following requirements:
- Obtain 50% of the points from the exercises for this course.
- Pass the final exam for this course.
Students who obtain enough points in the exercises, but fail to attend or pass the final exam, are eligible for a reexamination.
Students who do not obtain enough points in the exercises may attend the final exam, but they will not obtain a certificate, even when passing the exam.