# Seminar Logic, Complexity, Games: Fixed-Point Logics

## WS 2023/24

### Registration

• Computer Science: You can only apply via the central distribution system (SuPra). Please be aware of the deadlines.

• Mathematics: Please apply until Sunday, 18th June at 23:59 via e-mail to seminar@logic.rwth-aachen.de. Your application should include your full name, matriculation number, course of studies, semester and information about relevant courses you have passed (especially lectures from our group). If you would like to participate but you have missed the deadline, you should still apply, however, please be aware that the seminar might be full.

### Information

• seminar literature: TBA

• kick-off meeting: October 2023, the exact date will be announced

### Organisation

The presentations will take place as a block seminar at the end of the semester.

• Language: you may choose between English and German
• Length of seminar paper: around 7 pages
• Duration of presentation: 25 minutes

### Content

Fixed-point logics are of fundamental importance in many branches of logic and computer science, including finite model theory, verification, knowledge representation, complexity theory, and databases. They extend a basic logical formalism (such as first-order logic, propositional modal logic, or conjunctive queries) by the possibility to define fixed-points of relational operators. Fixed-point logics come in many incarnations and variations, depending on the kind of relational operators that are used, on the kind of fixed-points (least and greatest fixed points, inflationary and deflationary fixed points, partial fixed points, simultaneous inductions, etc.) and on the combination and interaction with other logical operators.

In finite model theory, fixed-point logics play a central role since they capture recursion and unbounded iteration in a natural and powerful way, and are of fundamental importance in the quest of logics that capture complexity classes. In database theory, query languages based on fixed-points, such as Datalog and its extensions, are of interest since they allow to define queries that are not expressible in basic languages like SQL. The modal mu-calculus is an important formalism for the specification and verification and encompasses most of the commonly used modal and temporal logics used in that area. There also is a very close and important relationship of fixed-point logic with the theory of infinite games.

In the seminar, we shall study the structure, the model-theoretic properties, and the expressive power of different variants of fixed-point logic, and explore algorithmic problems that arise in the application of such formalisms in different areas of logic and computer science.

### Classification

• Informatik (B.Sc.)
• Mathematik (B.Sc.)
• Informatik (M.Sc.)
• Mathematik (M.Sc.)
• Grundlagen der Informatik (M.Sc.)
• Data Science (M.Sc.)
• Software Systems Engineering (M.Sc.)
• Media Informatics (M.Sc.)

### Prerequisites

• Mathematical Logic
• for B.Sc. Computer Science: Module "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

### Contact

Erich Grädel, Matthias Naaf, Sophie Brinke, Lovro Mrkonjić