Zhilin Wu

To be a theoretician!

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.