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

    Schedules and rooms

    Summary schedule Wednesday 09:15 - 12:00, Hebdomadaire, PER 21, Room F130 (Autumn semester)
    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 / 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/

    Softskills
    No
    Off field
    No
    BeNeFri
    Yes
    Mobility
    Yes
    UniPop
    No
  • Dates and rooms
    Date Hour Type of lesson Place
    21.09.2022 09:15 - 12:00 Cours PER 21, Room F130
    28.09.2022 09:15 - 12:00 Cours PER 21, Room F130
    05.10.2022 09:15 - 12:00 Cours PER 21, Room F130
    12.10.2022 09:15 - 12:00 Cours PER 21, Room F130
    19.10.2022 09:15 - 12:00 Cours PER 21, Room F130
    26.10.2022 09:15 - 12:00 Cours PER 21, Room F130
    02.11.2022 09:15 - 12:00 Cours PER 21, Room F130
    09.11.2022 09:15 - 12:00 Cours PER 21, Room F130
    16.11.2022 09:15 - 12:00 Cours PER 21, Room F130
    23.11.2022 09:15 - 12:00 Cours PER 21, Room F130
    30.11.2022 09:15 - 12:00 Cours PER 21, Room F130
    07.12.2022 09:15 - 12:00 Cours PER 21, Room F130
    14.12.2022 09:15 - 12:00 Cours PER 21, Room F130
    21.12.2022 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: 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 : 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