Automata on infinite structures

  • Enseignement

    Détails

    Faculté Faculté des sciences et de médecine
    Domaine Informatique
    Code UE-SIN.08502
    Langues Anglais
    Type d'enseignement Cours
    Cursus Master
    Semestre(s) SA-2021

    Horaires et salles

    Horaire résumé Mercredi 09:15 - 12:00, Hebdomadaire
    Struct. des horaires 3h par semaine durant 14 semaines
    Heures de contact 42

    Enseignement

    Responsables
    Enseignants
    Assistants
    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.

    Objectifs de formation

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

    Commentaire 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
    Non
    Hors domaine
    Non
    BeNeFri
    Oui
    Mobilité
    Oui
    UniPop
    Non
  • Dates et salles
    Date Heure Type d'enseignement Lieu
    22.09.2021 09:15 - 12:00 Cours PER 21, salle F130
    29.09.2021 09:15 - 12:00 Cours PER 21, salle F130
    06.10.2021 09:15 - 12:00 Cours PER 21, salle F130
    13.10.2021 09:15 - 12:00 Cours PER 21, salle F130
    20.10.2021 09:15 - 12:00 Cours PER 21, salle F130
    27.10.2021 09:15 - 12:00 Cours PER 21, salle F130
    03.11.2021 09:15 - 12:00 Cours PER 21, salle F130
    10.11.2021 09:15 - 12:00 Cours PER 21, salle F130
    17.11.2021 09:15 - 12:00 Cours PER 21, salle F130
    24.11.2021 09:15 - 12:00 Cours PER 21, salle F130
    01.12.2021 09:15 - 12:00 Cours PER 21, salle F130
    15.12.2021 09:15 - 12:00 Cours PER 21, salle F130
    22.12.2021 09:15 - 12:00 Cours PER 21, salle F130
  • Modalités d'évaluation

    Examen écrit

    Mode d'évaluation Par note
  • Affiliation
    Valable pour les plans d'études suivants:
    BcMa - Informatique de gestion - 30 ECTS
    Version: 2020/SA_V01
    Cours > Modules informatique > Logic

    Complément au doctorat [PRE-DOC]
    Version: 2020_1/v_01
    Complément au doctorat ( Faculté des sciences et de médecine) > UE de spécialisation en Informatique (niveau master)

    Enseignement complémentaire en sciences
    Version: ens_compl_sciences
    Paquet indépendant des branches > UE de spécialisation en Informatique (niveau master)

    Informatique [3e cycle]
    Version: 2015_1/V_01
    Formation continue > UE de spécialisation en Informatique (niveau master)

    Informatique [POST-DOC]
    Version: 2015_1/V_01
    Formation continue > UE de spécialisation en Informatique (niveau master)

    MSc en informatique (BeNeFri)
    Version: 2010_2/V_02
    MSc en informatique (BeNeFri), cours, séminaires et travail de Master > T4: Logic
    MSc en informatique (BeNeFri), cours, séminaires et travail de Master > UE de spécialisation en Informatique (niveau master)

    Ma - Business Communication : Informatique de gestion - 90 ECTS
    Version: 2020/SA_V01
    Cours - 60 ECTS > Groupe d'option > Informatique de gestion > Cours > Modules informatique > Logic

    Ma - Informatique de gestion - 90 ECTS
    Version: 2020/SA-v01
    Cours - min. 45 ECTS > Modules informatique/informatique de gestion > Logic

    Ma - Informatique de gestion - 90 ECTS
    Version: 2019/SA_V01
    Cours - min. 45 ECTS > Modules informatique/informatique de gestion > Logic