ΛΟΓΙΚΗ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗ ΙΙ: ΛΟΓΙΚΗ, ΑΥΤΟΜΑΤΑ ΚΑΙ ΠΑΙΓΝΙΑ (ΗΜΜΥ, ΕΜΕ), Ειδικά Θέματα Λογικής: Περιγραφική Πολυπλοκότητα (ΑΛΜΑ-ΕΜΕ)
Section outline
-
Λογική, Αυτόματα και Παίγνια
Θα μελετήσουμε τη σχέση Λογικής, Αυτομάτων και Παιγνίων.
Προαπαιτούμενα: Τουλάχιστον ένα μάθημα Μαθηματικής Λογικής και ένα Αυτομάτων.
Διδάσκοντες: Στάθης Ζάχος (zachos@cs.ntua.gr), Πέτρος Ποτίκας (ppotik@cs.ntua.gr)Έναρξη μαθήματος: 13/10/2026
Διαλέξεις: Τρίτη 15:15-17:00 και Πέμπτη 10:45-12:30, αιθ. 1.1.31, παλ. κτ. ΗΜΜΥ.Βιβλία
- Automata, Logics, and Infinite Games: A Guide to Current Research, Erich Grädel, Wolfgang Thomas, Thomas Wilke
- Automata Theory and Logic, Martin Hofmann and Martin Lange
- Tree Automata Techniques and Applications Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi (https://inria.hal.science/hal-03367725v1/file/tata.pdf)
- Finite model theory, Leon Libkin (https://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf), για EF games
- Descriptive complexity, Neil Immerman (https://people.cs.umass.edu/~immerman/book/ch6.pdf), για EF games
- Introduction to the Theory of Computation, Michael Sipser, για αυτόματα, τυπικές γλώσσες, γραμματικές
- Introduction to Automata Theory, Languages, and Computation, Jeffrey Ullman and John Hopcroft
- Μαθηματική Λογική, Γ. Κολέτσος, https://repository.kallipos.gr/handle/11419/2299?locale=el
-