Automata on infinite structures
-
Teaching
Details
Faculty Faculty of Science and Medicine Domain Computer Science Code UE-SIN.08502 Languages English Type of lesson Lecture
Level Master Semester SA-2021 Schedules and rooms
Summary schedule Wednesday 09:15 - 12:00, Hebdomadaire (Autumn semester)
Struct. of the schedule 3h par semaine durant 14 semaines Contact's hours 42 Teaching
Responsibles - Ultes-Nitsche Ulrich
Teachers - Ultes-Nitsche Ulrich
Assistants - Stammet Christophe
Description In this course unit, we deal with a fraction of automata theory that is applied when it comes to representing behaviours of reactive systems (OS, communications protocols, control systems, etc.). The common abstraction of the indefinite running time of such systems is the assumption that they run forever, leading to automata models operating on infinite sequences or trees. We will explore different equivalent models of automata on infinite words, namely Büchi, Muller, and Rabin Automata. We will learn how to manipulate them algorithmically, and explore their relation to logic, in particular to the monadic second-order logic of one successor. Finally, we will look at what changes, when these automata are applied to infinite trees rather than infinite words. Training objectives After the completion of this course unit, the student will:
- know how to manipulate automata algorithmically
- be able to relate set operations to operations on the automaton level
- understand the limited expressiveness of finite-state automata
- see the link between logic and automata
- know how to exploit automata and logic to express properties of systemsComments MSc-CS BENEFRI - (Code Ue: 43024/ Tracks: T4)
The exact date and time of this course as well as the full course list can be found under http://diuf.unifr.ch/drupal/mcs/program/courses-timetable/courses.Softskills No Off field No BeNeFri Yes Mobility Yes UniPop No -
Dates and rooms
Date Hour Type of lesson Place 22.09.2021 09:15 - 12:00 Cours PER 21, Room F130 29.09.2021 09:15 - 12:00 Cours PER 21, Room F130 06.10.2021 09:15 - 12:00 Cours PER 21, Room F130 13.10.2021 09:15 - 12:00 Cours PER 21, Room F130 20.10.2021 09:15 - 12:00 Cours PER 21, Room F130 27.10.2021 09:15 - 12:00 Cours PER 21, Room F130 03.11.2021 09:15 - 12:00 Cours PER 21, Room F130 10.11.2021 09:15 - 12:00 Cours PER 21, Room F130 17.11.2021 09:15 - 12:00 Cours PER 21, Room F130 24.11.2021 09:15 - 12:00 Cours PER 21, Room F130 01.12.2021 09:15 - 12:00 Cours PER 21, Room F130 15.12.2021 09:15 - 12:00 Cours PER 21, Room F130 22.12.2021 09:15 - 12:00 Cours PER 21, Room F130 -
Assessments methods
Written exam
Assessments methods By rating -
Assignment
Valid for the following curricula: Additional Courses in Sciences
Version: ens_compl_sciences
Paquet indépendant des branches > Specialized courses in Computer Science (Master level)
Additional programme requirements for PhD studies [PRE-DOC]
Version: 2020_1/v_01
Additional programme requirements for PhD studies (Faculty of Science and Medicine) > Specialized courses in Computer Science (Master level)
Computer Science [3e cycle]
Version: 2015_1/V_01
Continuing education > Specialized courses in Computer Science (Master level)
Computer Science [POST-DOC]
Version: 2015_1/V_01
Continuing education > Specialized courses in Computer Science (Master level)
MSc in Computer science (BeNeFri)
Version: 2023_1/V_01
MSc in Computer science (BeNeFri), lectures, seminars and Master thesis > T4 : Theory and Logic
Ma - Business Communication : Business Informatics - 90 ECTS
Version: 2020/SA_V02
Courses - 60 ECTS > Option Group > Information Management > Cours > Module Informatik > Logic
Ma - Business Informatics - 90 ECTS
Version: 2020/SA-v01
Classes - min. 45 ECTS > Module IT and IT Management > Logic
Ma - Information Management - 90 ECTS
Version: 2019/SA_V01
Classes - min. 45 ECTS > Module IT and IT Management > Logic
MiMa - Business Informatics - 30 ECTS
Version: 2020/SA_V01
Cours > Module Informatik > Logic