Automata on infinite structures
-
Unterricht
Details
Fakultät Math.-Nat. und Med. Fakultät Bereich Informatik Code UE-SIN.08502 Sprachen Englisch Art der Unterrichtseinheit Vorlesung
Kursus Master Semester SA-2021 Zeitplan und Räume
Vorlesungszeiten Mittwoch 09:15 - 12:00, Wöchentlich (Herbstsemester)
Strukturpläne 3h par semaine durant 14 semaines Kontaktstunden 42 Unterricht
Verantwortliche - Ultes-Nitsche Ulrich
Dozenten-innen - Ultes-Nitsche Ulrich
Assistenten - Stammet Christophe
Beschreibung 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.
Lernziele 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 systemsBemerkungen 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.Soft Skills Nein ausserhalb des Bereichs Nein BeNeFri Ja Mobilität Ja UniPop Nein -
Einzeltermine und Räume
Datum Zeit Art der Unterrichtseinheit Ort 22.09.2021 09:15 - 12:00 Kurs PER 21, Raum F130 29.09.2021 09:15 - 12:00 Kurs PER 21, Raum F130 06.10.2021 09:15 - 12:00 Kurs PER 21, Raum F130 13.10.2021 09:15 - 12:00 Kurs PER 21, Raum F130 20.10.2021 09:15 - 12:00 Kurs PER 21, Raum F130 27.10.2021 09:15 - 12:00 Kurs PER 21, Raum F130 03.11.2021 09:15 - 12:00 Kurs PER 21, Raum F130 10.11.2021 09:15 - 12:00 Kurs PER 21, Raum F130 17.11.2021 09:15 - 12:00 Kurs PER 21, Raum F130 24.11.2021 09:15 - 12:00 Kurs PER 21, Raum F130 01.12.2021 09:15 - 12:00 Kurs PER 21, Raum F130 15.12.2021 09:15 - 12:00 Kurs PER 21, Raum F130 22.12.2021 09:15 - 12:00 Kurs PER 21, Raum F130 -
Leistungskontrolle
Schriftliche Prüfung
Bewertungsmodus Nach Note -
Zuordnung
Zählt für die folgenden Studienpläne: Ergänzende Lehrveranstaltungen in Naturwissenschaften
Version: ens_compl_sciences
Paquet indépendant des branches > UE für Vertiefungsstudium in Informatik (Niveau Master)
Informatik [3e cycle]
Version: 2015_1/V_01
Weiterbildung > UE für Vertiefungsstudium in Informatik (Niveau Master)
Informatik [POST-DOC]
Version: 2015_1/V_01
Weiterbildung > UE für Vertiefungsstudium in Informatik (Niveau Master)
MSc in Informatik (BeNeFri)
Version: 2023_1/V_01
MSc in Informatik (BeNeFri), Vorlesungen, Seminare und Masterarbeit > T4 : Theory and Logic
Ma - Business Communication : Wirtschaftsinformatik - 90 ECTS
Version: 2020/SA_V02
Kurse - 60 ECTS > Optionsgruppe > Wirtschaftsinformatik > Kurse > Module Informatik > Theory and Logic
Ma - Wirtschaftsinformatik - 90 ECTS
Version: 2020/SA-v01
Kurse - min. 45 ECTS > Module Wirtschaftsinformatik/Informatik > Theory and Logic
NfMa - Wirtschaftsinformatik - 30 ECTS
Version: 2020/SA_V01
Kurse > Module Informatik > Theory and Logic
Zusatz zum Doktorat [PRE-DOC]
Version: 2020_1/v_01
Zusatz zum Doktorat (Math.-Nat. und Med. Fakultät) > UE für Vertiefungsstudium in Informatik (Niveau Master)