Formal Language Theory
| Title | ΘΕΩΡΙΑ ΤΥΠΙΚΩΝ ΓΛΩΣΣΩΝ / Formal Language Theory |
| Code | 0838 |
| Faculty | Sciences |
| School | Mathematics |
| Cycle / Level | 1st / Undergraduate, 2nd / Postgraduate |
| Teaching Period | Winter |
| Coordinator | Georgios Rachonis |
| Common | Yes |
| Status | Active |
| Course ID | 40000060 |
Programme of Study: PMS Tmīmatos Mathīmatikṓn (2018-sīmera)
Registered students: 9
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| THEŌRĪTIKĪ PLĪROFORIKĪ KAI THEŌRIA SYSTĪMATŌN KAI ELEGCΗOU | Core Courses | 1 | 1 | 10 |
| STATISTIKĪ KAI MONTELOPOIĪSĪ | Compulsory Course | 1 | 1 | 10 |
| Academic Year | 2018 – 2019 |
| Class Period | Winter |
| Faculty Instructors |
|
| Weekly Hours | 3 |
| Class ID | 600125741
|
Course Type 2016-2020
- Background
- Scientific Area
- Skills Development
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600125741
- Other: http://users.auth.gr/grahonis/TFL.html
Language of Instruction
- Greek (Instruction, Examination)
- English (Instruction)
Learning Outcomes
The students learn the concept of ω-recognizabilitty via the two types of automata, namely Büchi and Muller. They study the properties of the class of ω-recognizable langiages. They understand the differences among the aforementioned class and the class of recognizable languages. They are introduced to the notion of MSO logic and its expressive equivalence to recognizability (and ω-recognizability). Fially, they understand the important contribution of the above to practical apllications.
General Competences
- Apply knowledge in practice
- Retrieve, analyse and synthesise data and information, with the use of necessary technologies
- Adapt to new situations
- Make decisions
- Work autonomously
- Work in teams
- Work in an international context
- Work in an interdisciplinary team
- Generate new research ideas
- Design and manage projects
- Be critical and self-critical
- Advance free, creative and causative thinking
Course Content (Syllabus)
Alphabtes. Infinite words and ω-langugages. Automata over infinite words: Büchi and Muller recognizability. ω-Recognizable languages. Properties of ω-recognizable languages. The complementation problem of ω-recognizable languages. Monadic second-order logic. Equivalenvce of automata and MSO logic over infinite words. Applications of automata over infinite words to model checking.
Keywords
Automata over infinite words, ω-recognizable languages, monadic second-order logic
Educational Material Types
- Notes
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 39 | 1.3 | ✓ | ||
| Reading Assigment | 117 | 3.9 | ✓ | ||
| Total | 156 | 5.2 |
Student Assessment
Student Assessment methods
- Written Assignment (Formative, Summative)
- Oral Exams (Formative)
Bibliography
Additional bibliography for study
- C. Baier, J.-P. Katoen, Principles in model checking, MIT Press, 2008.
B. Khoussainov, A. Nerode, Automata Theory and its Applications, Birkhäuser
Boston, 2001.
- W. Thomas, Automata on infinite objects, in: Handbook of Theoretical Computer
Science, vol. B (J. v. Leeuwen, ed.), Elsevier Science Publishers, Amsterdam
1990, pp. 135-191.
- W. Thomas, Languages, automata and logic, in: Handbook of Formal Languages, vol.
3 (G. Rozenberg, A. Salomaa, eds.), Springer, 1997, pp. 389-485.
- M-H. Tsai, S. Fogarty, M.Y. Vardi, Y-K. Tsay, State of Büchi complementation,
Full version of CIAA 2010 paper,
http://www.cs.rice.edu/~vardi/papers/ciaa10rj.pdf
- Q. Yan, Lower bounds for complementation of omega-automata via the full automata
technique, Logical Methods in Computer Science 4(2005), 1-20.
Last Update
25-09-2018
