Logic, Games and Automata

6 EC

Semester 2, period 5

5314LOGA6Y

Owner Master Logic
Coordinator dr. B. Afshari
Part of Master Logic,

Course manual 2020/2021

Course content

This course will introduce the student to the mathematical theory underlying reactive systems, typically finite state systems that maintain an ongoing interaction with their environment. We will study the theory through three theoretical formalisms: Logic, Games and Automata. Automata are a powerful model of computation for state-based systems. Logic provides a formal language for the specification of correctness properties. Using the idea of two-player games we will build mathematical models of the system-environment interaction.

Study materials

Literature

  • S. Demri, V. Goranko, and M. Lange. Temporal Logics in Computer Science: Finite-State Systems. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2016.

Other

  • Lecture slides/notes will be provided through the course homepage.

Objectives

  • demonstrate an understanding of the mathematical theory underlying state-based systems through the formalisms of Logic, Games and Automata
  • express computational properties of finite state-based systems as problems in the language of logic, games and automata
  • analyse key concepts in connection with the three formalisms

Teaching methods

  • Lecture
  • Supervision/feedback meeting
  • Self-study

Learning activities

Activity

Hours

Hoorcollege

28

Tentamen

3

Werkcollege

14

Self study

123

Total

168

(6 EC x 28 uur)

Attendance

This programme does not have requirements concerning attendance (TER-B).

Assessment

Item and weight Details

Final grade

7 (70%)

Tentamen

3 (30%)

Weekly Assignments

To pass the course must obtain at least 50% on the exam component. Any missed weekly assignments are graded as 1. There is no resit opportunity for the weekly assignment component.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Timetable

The schedule for this course is published on DataNose.

Contact information

Coordinator

  • dr. B. Afshari