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.


Latest draft: book-20090701.pdf

List of contents


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.