Course on Logic and Automata Theory
course is intended as an introduction to elementary decision techniques
for various logic using automata theory. The focus will be on the
connection between various logics and types of automata.
In addition to the standard material, there will be two invited
lecturers who will develop the following related topics:
students taking this course are expected to be familiar with basic set
theoretic notions (relations, functions, orders, etc) as well as with
boolean and predicate logic (e.g. understand the meaning
of boolean connectors and first-order quantifiers). Students who do not
have these notions must contact the instructor.
- Florent Garnier (Verimag)
: probabilistic automata (curriculum can be found here)
- Polyvios Pratikakis
(Verimag) : lambda calculus and type theory (curriculum can be found here)
A course syllabus can be found here
Lecture notes are available here (postscript).
All lectures will be held in english.
Slides for the lectures are available here (PDF):
- W. Thomas. Handbook of Theoretical Computer Science, Volume B,
Chapter 4. Automata on Infinite
Objects pages 135-164
- B. Khoussainov and A. Nerode. Automata
Theory and its Applications ISBN 0-8176-4207-2
- Tree Automata Techniques and
Applications Collective Online Book
Lambda Calculus and Type Systems
- R.G. Bukharaev. Probabilistic
- C. Baier, M. Grosser. Recognizing omega-regular languages with
- B. C. Pierce. Types and
Programming Languages. MIT Press 2002
- H. Barendregt. Lambda
Calculi with Types. Handbook of Logic in Computer Science.
- P. Wadler. Proofs
are Programs: 19th Century Logic and 21st Century Computing
- M. Heine et al. Lectures
on the Curry-Howard Isomorphism
For additional questions please contact the instructor:
radu_._iosif_@_imag_._fr (please remove the _'s)