Graduate course: Automata theory and its applications

Syllabus
- Extensive introduction to automata theory and its applications
- Automata over finite words, infinite words, finite (ranked and unranked) trees, infinite trees
- Applications: Formal verification, XML document processing
Slides
- Lecture 1: Historical perspective, course syllabus and basic concepts
- Lecture 2: Chomsky Hierarchy - Overview and Turing machines
- Lecture 3-4: Chomsky Hierarchy - Context sensitive and free languages
- Lecture 5-6: Chomsky Hierarchy - Regular languages
- Lecture 7-8: Visibly pushdown languages
- Lecture 9-11: Automata over infinite words
- Lecture 12-14: Automata over ranked finite trees
- Lecture 15-16: Automata over (ranked) infinite trees
- Lecture 17-18: Automata over unranked trees
- Lecture 19-20: Automata-theoretical approach to model checking
- Lecture 21-22: Automata for XML
- Lecture 23: Antichains: A New Algorithm for Checking Universality of Finite Automata , Presented by Peng Zhou
- Lecture 24: Determinization of Buchi-Automata , Presented by Weifeng Wang
- Lecture 25: Visibly Rational Expressions , Presented by Ping Lu
- Lecture 26: Relating word and tree automata , Presented by Zhaowei Xu
- Lecture 27: Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages , Presented by Wenbo Lian
- Lecture 28: Deterministic Automata for the (F,G)-fragment of LTL , Presented by Miao Xie
- Lecture 29: Unranked tree automata with sibling equalities and disequalities , Presented by Xu Gao
References
- Pages 107-232, Introduction to Automata theory, languages and computation (J. E. Hopcroft, J. D. Ullman).
- Pages 1-112, Automata and computability (D. Kozen, Springer, 1997).
- R. Alur, P. Madhusudan, Visibly pushdown languages, STOC 2004.
- Berndt Farwer, Omega automata, Automata, logic and infinite games, Chapter 1.
- W. Thomas, Automata on infinite objects, Handbook of Theoretical Computer Science, vol. B, Chapter 4.
- W. Thomas, Languages, automata and logics, Handbook of formal languages, vol. 3, Pages 389 – 455.
- Pages 11-50, Pages 199-258, Tree automata, techniques and applications (H. Comon, M. Dauchet, et. al. 2007).
- T. Schwentick, Automata for XML--A survey, Journal of Computer and System Sciences, vol. 73(3), 2007, Pages 289-315.
Homework
- Homework-01
- Homework-02
- Homework-03 (By Ping Lu)      Homework-03 (By Weifeng Wang)
- Homework-04
- Homework-05
Paper list for reading project
- 1. Martin De Wulf, Laurent Doyen, Thomas A. Henzinger, Jean-François Raskin. Antichains: A New Algorithm for Checking Universality of Finite Automata. Proceedings of CAV 2006, LNCS 4144, Springer-Verlag, 17-30, 2006.
- 2. Markus Roggenbach, Determinization of Buchi-Automata, Chapter 3, Automata, logics, and infinite games, LNCS 2500, 43-60, 2002.
- 3. Laura Bozzelli, Cesar Sanchez, Visibly Rational Expressions, FSTTCS 2012, 211-223, 2012.
- 4. M. Bojanczyk and T. Colcombet. Tree-walking automata do not recognize all regular languages. In ACM Symposium on the Theory of Computing, pages 234– 243, 2005.
- 5. W. Karianto, C. Loding, Unranked tree automata with sibling equalities and disequalities. In Proc. ICALP 2007. LNCS 4596, 875-887, 2007.
- 6. Orna Kupfermana, Shmuel Safra, Moshe Y. Vardi, Relating word and tree automata, Annals of Pure and Applied Logic, Volume 138, Issues 1–3, 126–146, 2006.
- 7. Jan Kretinsky, Javier Esparza, Deterministic Automata for the (F,G)-fragment of LTL, CAV 2012.
- 8. Wouter Gelade, Tomasz Idziaszek, Wim Martens, Frank Neven, Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages, PODS 2010, 251-260.