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-2022

    Zeitplan und Räume

    Vorlesungszeiten Mittwoch 09:15 - 12:00, Wöchentlich, PER 21, Raum F130 (Herbstsemester)
    Strukturpläne 3h par semaine durant 14 semaines
    Kontaktstunden 42

    Unterricht

    Verantwortliche
    Dozenten-innen
    Assistenten
    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 systems

    Bemerkungen

    MSc-CS BENEFRI - (Code Ue: 43024 / Track: T4) The exact date and time of this course as well as the complete course list can be found at http://mcs.unibnf.ch/.

    Course and exam registration on ACADEMIA (not myunifr.ch). Please follow the instructions on https://mcs.unibnf.ch/organization/

    Soft Skills
    Nein
    ausserhalb des Bereichs
    Nein
    BeNeFri
    Ja
    Mobilität
    Ja
    UniPop
    Nein
  • Einzeltermine und Räume
    Datum Zeit Art der Unterrichtseinheit Ort
    21.09.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    28.09.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    05.10.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    12.10.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    19.10.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    26.10.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    02.11.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    09.11.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    16.11.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    23.11.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    30.11.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    07.12.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    14.12.2022 09:15 - 12:00 Kurs PER 21, Raum F130
    21.12.2022 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)

    Ma - Business Communication : Wirtschaftsinformatik - 90 ECTS
    Version: 2020/SA_V01
    Kurse - 60 ECTS > Optionsgruppe > Wirtschaftsinformatik > Kurse > Module Informatik > Logic

    Ma - Wirtschaftsinformatik - 90 ECTS
    Version: 2020/SA-v01
    Kurse - min. 45 ECTS > Module Wirtschaftsinformatik/Informatik > Logic

    Ma - Wirtschaftsinformatik - 90 ECTS
    Version: 2019/SA_V01
    Kurse - min. 45 ECTS > Module Wirtschaftsinformatik/Informatik > Logic

    NfMa - Wirtschaftsinformatik - 30 ECTS
    Version: 2020/SA_V01
    Kurse > Module Informatik > 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)