Formal Language Theory

Course Information
TitleΘΕΩΡΙΑ ΤΥΠΙΚΩΝ ΓΛΩΣΣΩΝ / Formal Language Theory
Code0838
FacultySciences
SchoolMathematics
Cycle / Level1st / Undergraduate, 2nd / Postgraduate
Teaching PeriodWinter
CoordinatorGeorgios Rachonis
CommonYes
StatusActive
Course ID40000060

Programme of Study: PMS Tmīmatos Mathīmatikṓn (2018-sīmera)

Registered students: 6
OrientationAttendance TypeSemesterYearECTS
THEŌRĪTIKĪ PLĪROFORIKĪ KAI THEŌRIA SYSTĪMATŌN KAI ELEGCΗOUCore Courses1110
STATISTIKĪ KAI MONTELOPOIĪSĪCompulsory Course1110

Class Information
Academic Year2020 – 2021
Class PeriodWinter
Faculty Instructors
Weekly Hours3
Class ID
600181058
Course Type 2016-2020
  • Background
  • Scientific Area
  • Skills Development
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
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
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures391.3
Reading Assigment1173.9
Total1565.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