Introduction to Automatic Structures
Introduction to Automatic Structures
Lehrveranstaltung mit SWS 2/1/0 (Vorlesung/Übung/Praktikum) in SS 2016
Dozent
Tutor
Umfang (SWS)
- 2/1/0
Module
- Theorie der Programmierung Fachgebiet Theorie der Programmierung
- INF-BAS6
- INF-VERT6
- INF-B-510
- INF-B-520
- MCL-TCSL
- MCL-PI
- EMCL-A-TCSL
- EMCL-A-PI
Leistungskontrolle
- Mündliche Prüfung
Course Description
An automatic structure is one whose domain and atomic relations are computable by finite-state automata. The type of automata considered are those that operate synchronously on their inputs, which can be finite or infinite words or trees. The fundamental property of every automatic structure is that the first order definable relations are computable by automata.
The course will be devoted to the study of (mathematical) structures that can be described by finite state machines such as finite automata, tree automata and omega automata. In particular, we study
- mathematical and algorithmic properties of automata,
- algorithmic and logical properties of automatic structures, and
- typical mathematical structures that are described by automata, e.g. linear orders, Boolean algebras, graphs, and groups.
Organisation
The lecture takes place weekly on Mondays 13:00-14:30 (DS 4) in APB E005. All the material necessary for successfully approving the course will be presented during the lecture. Students are strongly recommended to copy the material written on the blackboard during lecture time.
The lecture is accompanied by exercise sessions given every second week on Tuesdays 09:20-10:50 (DS 2) in APB E005 Mondays 14:50-16:20 (DS 5) in APB 3027. All students are encouraged to present their solutions to the exercises, as they are useful for better understanding of the lecture material. Exercise sheets will be available online about a week before the session.
Prerequisites
- The course will use notions of automata theory, e.g. basic automata models.
- Solid knowledge of propositional and ideally also first order logic is helpful.
The lecture will be based on the following course material:
Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | Lecture | DS4, 4. April 2016 in APB E005 | |
| Vorlesung | Lecture | DS4, 11. April 2016 in APB E005 | |
| Übung | Tutorial 1 | DS5, 11. April 2016 in APB 3027 | Datei |
| Vorlesung | Lecture | DS4, 18. April 2016 in APB E005 | |
| Vorlesung | Lecture | DS4, 25. April 2016 in APB E005 | |
| Übung | Tutorial 2 | DS5, 25. April 2016 in APB 3027 | Datei |
| Vorlesung | Lecture | DS4, 2. Mai 2016 in APB E005 | |
| Vorlesung | Lecture | DS4, 9. Mai 2016 in APB E005 | |
| Übung | Tutorial 3 | DS5, 9. Mai 2016 in APB 3027 | Datei |
| Vorlesung | Lecture | DS4, 23. Mai 2016 in APB E005 | |
| Übung | Tutorial 4 | DS5, 23. Mai 2016 in APB 3027 | Datei |
| Vorlesung | Lecture | DS4, 30. Mai 2016 in APB E005 | |
| Vorlesung | Lecture | DS4, 6. Juni 2016 in APB E005 | |
| Übung | Tutorial 5 | DS5, 6. Juni 2016 in APB 3027 | Datei |
| Vorlesung | Lecture | DS4, 13. Juni 2016 in APB E005 | |
| Übung | Tutorial 5 (continued) | DS5, 13. Juni 2016 in APB 3027 | |
| Vorlesung | Lecture | DS4, 20. Juni 2016 in APB E005 | |
| Vorlesung | Lecture | DS4, 27. Juni 2016 in APB E005 | |
| Übung | Tutorial 6 | DS5, 27. Juni 2016 in APB 3027 | |
| Vorlesung | Lecture | DS4, 4. Juli 2016 in APB E005 | |
| Vorlesung | Lecture | DS4, 11. Juli 2016 in APB E005 | |
| Übung | Tutorial 7 | DS5, 11. Juli 2016 in APB 3027 |
Kalender
