Computational Model TheoryModule description #41250 / Version 1
- 9 CP
- Oral exam
- Graded
- Summer semester
- English
| Module / Version | #41250 / #1 |
|---|---|
| Validity | Since Summer semester 2025 |
| Available language(s) | English |
| Credit points | 9 |
| Person responsible for the module | Kreutzer, Stephan |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | English |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34352200 FG Logik und Semantik (LaS) |
Contact
| Office | EN 25 |
|---|---|
| Contact person | Kreutzer, Stephan |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | https://www.tu.berlin/las/studium-lehre/veranstaltungsangebot |
Learning outcomes
At the end of the course student will
- be familiar with several important techniques from logic that can be facilitated to obtain algorithmic results
- have a good overview of important classes of graphs that are particularly well-suited for algorithmic applications
- be familiar with the structral properties of these classes and how they can be exploited algorithmically
- be able to employ the various tools learned in this course to develop efficient parameterized algorithms for hard computational problems on specific classes of input structures.
- be familiar with several important techniques from logic that can be facilitated to obtain algorithmic results
- have a good overview of important classes of graphs that are particularly well-suited for algorithmic applications
- be familiar with the structral properties of these classes and how they can be exploited algorithmically
- be able to employ the various tools learned in this course to develop efficient parameterized algorithms for hard computational problems on specific classes of input structures.
Content
As the starting point of this course we consider the simple question "How complex is it to evalute a sentence of first-order logic in a finite structure or graph". This question has a simple answer in classical complexity theory: the problem is PSPACE complete and remains so even for a fixed input graph with at least two vertices. On the other hand, if we fix the input formula the problem becomes polynomial time solvable.
The answer to this question becomes much more interesting in the context of parameterized complexity. That is, we ask under which circumstances can we evaluate a first-order sentence in a finite graph in time polynomial in the size of the graph (but with arbitrary dependence on the formula size). Under standard assumptions in complexity theory this will not be possible for all graphs or structures, but if additional restrictions are imposed on the input structure then such running time can be achieved.
In the quest to fully understand the structural restrictions that need to be imposed on the class of admissible input graphs to make such algorithms possible, a very rich and fruitful theory of the interplay between logic and structural graph theory has emerged. That is, in this field methods from computational logic and model theory are combined with methods from structural and algorithmic graph theory to achieve efficient evaluation algorithms for first-order sentences.
As a side effect, many of these methods have found numerous applications in graph algorithms and algorithms for hard computational problems.
In this course we will study several of these methods. More precisely, we will look at various structural parameters for graphs such as tree-width, tree-depth, nowhere denseness and other, identify their properties that can be exploited algorithmically, develop algorithms for NP-complete problems on these classes and finally see how this can be used to obtain efficient algorithms for first-order model checking.
At the end of the course students will have a good overview of several important graph classes and their algorithmic properties as well as a good command of the logical tools that can be employed to speed up computation and model-checking on these classes of graphs.
The most interesting aspect of this course is the way the methods from graph theory, algorithmics, and logic interact to get the results we want. As another highlight we will cover very recent results on dense classes of graphs that lead us very close to current and ongoing research problems.
The answer to this question becomes much more interesting in the context of parameterized complexity. That is, we ask under which circumstances can we evaluate a first-order sentence in a finite graph in time polynomial in the size of the graph (but with arbitrary dependence on the formula size). Under standard assumptions in complexity theory this will not be possible for all graphs or structures, but if additional restrictions are imposed on the input structure then such running time can be achieved.
In the quest to fully understand the structural restrictions that need to be imposed on the class of admissible input graphs to make such algorithms possible, a very rich and fruitful theory of the interplay between logic and structural graph theory has emerged. That is, in this field methods from computational logic and model theory are combined with methods from structural and algorithmic graph theory to achieve efficient evaluation algorithms for first-order sentences.
As a side effect, many of these methods have found numerous applications in graph algorithms and algorithms for hard computational problems.
In this course we will study several of these methods. More precisely, we will look at various structural parameters for graphs such as tree-width, tree-depth, nowhere denseness and other, identify their properties that can be exploited algorithmically, develop algorithms for NP-complete problems on these classes and finally see how this can be used to obtain efficient algorithms for first-order model checking.
At the end of the course students will have a good overview of several important graph classes and their algorithmic properties as well as a good command of the logical tools that can be employed to speed up computation and model-checking on these classes of graphs.
The most interesting aspect of this course is the way the methods from graph theory, algorithmics, and logic interact to get the results we want. As another highlight we will cover very recent results on dense classes of graphs that lead us very close to current and ongoing research problems.
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Computational Model Theory | Integrated course | Irregular | [en] | 6 | ISIS |
Workload and credit points
Computational Model Theory (Integrated course)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 6 h | 90 h |
| Pre/post processing | 15 | 12 h | 180 h |
| 270 h | |||
The workload of the module adds up to 270 hours. The module therefore comprises 9 credit points.
Description of teaching and learning methods
The course will comprise a series of lectures and tutorials used to deepen the understanding of the concepts covered in the lectures.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
There are no formal prerequisites for this course as we will introduce the concepts we use from scratch.
However students are expected to be familiar with basic concepts of logic, especially first-order predicate logic as they are taught in the undergraduate course "Logik" in the computer science curriculum. Furthermore, basic knowledge of graph theory is helpful but these will be recalled in the course.
In any case, students should have a strong interest in theoretical computer science and sufficient "mathematical maturity".
However students are expected to be familiar with basic concepts of logic, especially first-order predicate logic as they are taught in the undergraduate course "Logik" in the computer science curriculum. Furthermore, basic knowledge of graph theory is helpful but these will be recalled in the course.
In any case, students should have a strong interest in theoretical computer science and sufficient "mathematical maturity".
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | English, German |
| Duration/Extent | 20-45 Minuten |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Students can sign up for this course on the ISIS page. At the end of the term there will be an oral exam for which students can sign up in the usual way towards the end of the lecture period.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
No recommended literature given
Assigned programs
This module version is used in the following programs:
| Program / program version | Semester(s) | Curriculum component |
|---|---|---|
| Computer Engineering Computer Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science (Informatik) Computer Science (Informatik) (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Electrical Engineering Electrical Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
Miscellaneous
Not specified