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

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

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

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

Γενικά

Διδάσκων

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

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

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

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

Τρίτη, 7 Μαρτίου 2017

Διαλέξεις

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

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

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

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

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

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

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

Η/Μ Ομιλητής Θέμα - Περιεχόμενο
7/3/2017
Θ. Παπαμακάριος		 Εισαγωγή - Διαδικαστικά
Proof Complexity
14/3/2017 Θ. Παπαμακάριος Proof Complexity (cont'd)
21/3/2017 Α. Χαλκή Infinite Automata (slides)
28/3/2017 A. Χαλκή Ehrenfeucht-Fraisse Games
Inexpressibility in First Order Logic (slides)
4/4/2017 Κώστας Τσαπρούνης Large Cardinal Axioms (slides)
25/4/2017 Κώστας Τσαπρούνης Large Cardinal Axioms (cont'd) (slides)
2/5/2017 Πέτρος Ποτίκας Introduction to Modal Logic (slides)
9/5/2017 Πέτρος Ποτίκας Decidability of Modal Logic (slides)
16/5/2017 Γιώργος Πιτσιλαδής Introduction to π-calculus (slides)
23/5/2017 Θ. Παπαμακάριος Tableaux approach to Proof Complexity
30/5/2017 Ν. Κωτσάνη Translating Modal Logic into FOL and SOL (slides)
6/6/2017 Α. Χαλκή Linear Temporal Logic (LTL)
13/6/2017 Π. Πατσιλινάκος Infinite Combinatorics (slides)
20/6/2017 Σ. Πετσαλάκης μ-Calculus

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

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.

Large Cardinal Axioms

  • Γ. Μοσχοβάκης. Σημειώσεις στη Συνολοθεωρία. Νεφέλη, 1993
  • W. Just, M. Weese. Discovering Modern Set Theory I: The Basics. Graduate Studies in Mathematics, Vol. 8, American Mathematical Society, 1996.
  • K. Kunen. Set Theory: An introduction to independence proofs. Studies In Logic and The Foundations of Mathematics, Vol. 102, North-Holland, 1980.
  • A. Kanamori. The Higher Infinite. Springer-Verlag, 1994.
  • T. Jech. Set Theory, The Third Millennium Edition. Springer, 2002.
  • F. Drake. Set Theory: An Introduction to Large Cardinals. Studies in Logic & the Foundations of Mathematics, Vol 76, North-Holland, 1974.
  • W. Just, M. Weese. Discovering Modern Set Theory II: Set-Theoretic Tools for Every Mathematician. Graduate Studies in Mathematics, Vol. 18, American Mathematical Society, 1997.

Linear Temporal Logic

μ-Calculus