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 | No |
| Status | Active |
| Course ID | 40000060 |
Programme of Study: PMS Tmīmatos Mathīmatikṓn (2018-sīmera)
Registered students: 0
| 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 |
| Academic Year | 2013 – 2014 |
| Class Period | Winter |
| Faculty Instructors | |
| Weekly Hours | 3 |
| Class ID | 40049471
|
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/40049471
- Other: http://users.auth.gr/grahonis/TFL.html
Language of Instruction
- Greek (Instruction, Examination)
- English (Instruction)
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 | 10 | 0.3 | ✓ | ||
| Total | 49 | 1.6 |
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
09-07-2013
