Θεωρητική Πληροφορική ΙΙ:
Ειδικά Θέματα Λογικής (ΜΠΛΑ, ΑΛΜΑ)

Λογική, Αυτόματα και Παίγνια (ΣΗΜΜΥ)

εαρινό εξάμηνο 2017-2018

● Γενικά ● Ανακοινώσεις ● Διαλέξεις-Παρουσιάσεις ● Υλικό-Βιβλιογραφία ●

Γενικά

Διδάσκων

  • Στάθης Ζάχος, Καθηγητής ()

Βοηθός διδασκαλίας

  • Αγγελική Χαλκή, Υ.Δ. ()

Έναρξη μαθήματος

Τρίτη, 20 Φεβρουαρίου 2018

Διαλέξεις

Τρίτη 11:30-14:30, αίθουσα 1.1.31 (παλαιό) Κτίριο Ηλεκτρολόγων, Ε.Μ.Π.

Ώρες Γραφείου

  • Τρίτη, 14:30-15:30, Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλαιά Κτίρια Ηλεκτρολόγων

Προαπαιτούμενα

Μαθήματα σε Θεωρία Υπολογισιμότητας και Μαθηματικής Λογικής.

Ανακοινώσεις

Διαλέξεις - Παρουσιάσεις

Η/Μ Ομιλητής Θέμα - Περιεχόμενο
20/2/2018 Διαδικαστικά - Εισαγωγή
27/2/2018 Π. Ποτίκας Intro to Finite Model Theory, Ehrenfeucht-Fraisse Games
6/3/2018 Α. Χαλκή Finite Model Theory: Locality
13/3/2018 Ε. Αναστασιάδη Finite Model Theory: Complexity
20/3/2018 Ε. Αναστασιάδη Finite Model Theory: Complexity (cont'd)
27/3/2018 A. Κάββος Finite Model Theory: Second Order Logic
3/4/2018 A. Κάββος Finite Model Theory: Second Order Logic, Strings, Tree Automata (cont'd)
17/4/2018 A. Σινγκ Λογικές με μέτρηση
24/4/2018 A. Σινγκ Λογικές με μέτρηση
15/5/2018 Θ. Παπαμακάριος Μηχανές Turing και πεπερασμένα μοντέλα
29/5/2018 Α. Χαλκή Fixed point logics (I)
5/6/2018 Α. Χαλκή Fixed point logics (II)
12/6/2018 Α. Χαλκή Fixed point logics (III)

Υλικό - Βιβλιογραφία

Modal Logic

  • P. Blackburn, M. de Rijke, Y. Venema, Modal Logic, Cambridge University Press, 2001.
  • R. Goldblatt, Logics of Time and Computation, CSLI Publications, 1992.
  • B. F. Chellas, Modal Logic - an introduction, Cambridge University Press, 1980.
  • M. Fitting, R. L. Mendelsohn, First Order Modal Logic, Kluwer Academic Publishers, 1998
  • M. Vardi. Why is modal logic so robustly decidable? In DIMACS Series in Discrete Mathematics and Theoretical Computer Science 31, pages 149-184. American Math. Society, 1997.
  • E. Grädel. Why are modal logics so robustly decidable? Bulletin of the EATCS, vol 68, 90-103, 1999.

Automata, Logics and Infinite Games

  • Σ. Ζάχος, Α. Παγουρτζής, Τα Θεμέλια της Πληροφορικής, εκδόσεις Τσότρας, 2014
  • Μ. Sipser. Introduction to the Theory of Computation.
  • J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
  • H. R. Lewis and C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
  • D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
  • M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
  • L. Libkin. Elements of Finite Model Theory. Springer (2012).
  • Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi. Tree Automata Techniques and Applications.
  • Editors: Erich Grädel, Wolfgang Thomas, Thomas Wilke. Automata Logics, and Infinite Games. A Guide to Current Research. Springer, Lecture Notes in Computer Science.

Proof Complexity

  • Grigori Tseitin. On the complexity of derivation in propositional calculus. Studies in constructive mathematics and mathematical logic, part 2, pages 115–125, 1968.
  • Stephen Cook and Robert Reckhow. The relative efficiency of propositional proof systems. Journal of Symbolic Logic, 44(1):36–50, 1979.
  • Robert Reckhow. On the lengths of proofs in the propositional calculus. PhD thesis, Department of Computer Science, University of Toronto, 1975.
  • Armin Haken. The intractability of resolution. Theoretical Computer Science, 39:297–308, 1985.
  • Vaŝek Chvátal and Endre Szemerédi. Many hard examples for resolution. J. ACM,35(4):759–768, 1988.
  • Alasdair Urquhart. Hard examples for resolution. J. ACM, 34(1):209–219, 1987.
  • Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow — resolution made simple. J. ACM, 48(2):149–169, 2001.

Finite Model Theory

Linear Temporal Logic

μ-Calculus