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, PER 21, Room F130
    Struct. of the schedule 3h par semaine durant 14 semaines
    Contact's hours 42

    Teaching

    Responsibles
    Teachers
    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.
    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 systems

    Comments 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

    Examen écrit

    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: 2010_2/V_02
    MSc in Computer science (BeNeFri), lectures, seminars and Master thesis > T4: Logic
    MSc in Computer science (BeNeFri), lectures, seminars and Master thesis > Specialized courses in Computer Science (Master level)

    Ma - Business Communication : Information Systems - 90 ECTS
    Version: 2020/SA_V01
    Courses - 60 ECTS > Option Group > Information Management > Cours > Module Informatik > Logic

    Ma - Information Management - 90 ECTS
    Version: 2019/SA_V01
    Classes - min. 45 ECTS > Module IT and IT Management > Logic

    Ma - Information Management - 90 ECTS
    Version: 2020/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