Automata on Infinite Words
» This course is given in English.
Lecture in winter term 2005/2006
| Type | Time/Place | Start | Lecturer |
|---|---|---|---|
| V2 | Tue 10:00 - 11:30 AH VI | 18.10.2005 | Thomas |
| Ü1 | Wed 17:00 - 17:45 AH II | 19.10.2005 | Thomas, Wöhrle, Rohde |
Contents
Finite automata on infinite words (omega-automata) are a vital means for the formal analysis of non-terminating systems (as used for e.g. managing processes and controlling factories). The results of the theory that will be presented in this lecture are employed for the automatic verification and synthesis of such systems.
The lecture focusses on the logical and algorithmic properties of omega-automata. Some of the topics covered are:
- Büchi automata,
- deterministic omega-automata,
- acceptance conditions and the classification of omega-languages,
- applications in logic and verification.
Previous Knowledge
The course is intended for students in their fifth semester. Basic knowledge of automata theory as presented in basic courses is required for participation.Combination with other courses
This course can be combined with the course "Unendliche Spiele" (C. Löding) to a full four hour course (V4, Ü2). In this combination, the material presented will roughly cover the contents of the course "Automata and Reactive Systems" from the winter term 2002/2003.
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.
Examination
To obtain a small certificate (V2, Ü1) or the credit points for this course, students have to meet the following requirements:
- Obtain a certain number (approx. 50%) of the points from the exercises for this course.
- Pass the final exam for this course.
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.
Credit Points
4 ECTS