Lecture note
General information
About "Introduction to Tree Language Theory"
This lecture course will provide you an introduction to tree language theory
in a self-contained manner. The course consists of 10 lectures. The first 6 lectures review the
introductory topics: tree automata and term rewriting together with some basics of formal languages
including
finite automata, computability, and complexity. Each lecture can be useful for
undergraduate/graduate students in learning
or reviewing tree automata and the background.
The remaining 4 lectures explain advanced topics, such as
Parikh's theorem (theory of commutative languages),
equational tree automata (ETA) and the further extensions from
monotone equational tree automata (MTA) to the recent and on-going frameworks,
propositional tree automata (PTA) and tree automata with normalization (TAN).
The characterization of each tree automata framework can be studied through
the discussion about the decidability, closure properties, and the relationship
to arithmetic logics.
Those who are interested in technical details
(such as omitted proofs and open questions)
are recommended to see
our papers. When you find errors in the
lecture note or you have suggestions for betterment,
kindly ask you to contact the author.
Download
Latest draft: book-20090701.pdf
List of contents
- Section 1: Words (and Monadic Second-Order Logic as an advanced topic)
- Section 2: Grammar
- Section 3: Trees
- Section 4: Modulo axioms
- Section 5: Turing machine
- Section 6: P, NP and PSPACE
- Section 7: Parikh's theorem
- Section 8: Equational tree automata
- Section 9: Monotone tree automata (MTA)
- Section 10: MTA and further extensions...
Acknowledgment
The author would like to deeply thank prof. Hiroyuki Seki of NAIST (Japan) for his advices and detailed comments overall about the text. I'm also grateful to many comments from people whom I met at University of Illinois at Urbana-Champaign (UIUC), in particular, Peter Csaba Ölveczky of University of Oslo, prof. José Meseguer and his students including Joe Hendrix, Mike Katelman, Camilo Rocha, Ralf Sasse. The first draft of this course note was accomplished when I visited at UIUC for a year in June 2007 - June 2008. Since then, the text has been revised, particularly, based on questions and comments obtained at 4th International School on Rewriting (ISR'09). I'd like to thank all attendees of my lectures for their contributions.
Copyright notice
All rights reserved. The lecturenote "Introduction to Tree Language Theory" is distributed by and copyrighted to Hitoshi Ohsaki, AIST. No part of this lecture note may be reproduced without the prior consent of the author.