E-Book Overview
This textbook presents the basics of tree automata. The authors discuss only finite tree automata, and focus on the operational aspects of tree automata. This book should appeal the reader who wants to have a simple presentation of the basics of tree automata, and to see how some variations on the idea of tree automata have provided a nice tool for solving difficult problems.
E-Book Content
Tree Automata Techniques and Applications Hubert Comon Max Dauchet Florent Jacquemard Denis Lugiez Marc Tommasi
R´ emi Gilleron Sophie Tison
Contents Introduction
9
Preliminaries
13
1 Recognizable Tree Languages and Finite Tree Automata 1.1 Finite Tree Automata . . . . . . . . . . . . . . . . . . . . . 1.2 The Pumping Lemma for Recognizable Tree Languages . . 1.3 Closure Properties of Recognizable Tree Languages . . . . . 1.4 Tree Homomorphisms . . . . . . . . . . . . . . . . . . . . . 1.5 Minimizing Tree Automata . . . . . . . . . . . . . . . . . . 1.6 Top Down Tree Automata . . . . . . . . . . . . . . . . . . . 1.7 Decision Problems and their Complexity . . . . . . . . . . . 1.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
17 18 26 27 29 33 36 37 41 45
2 Regular Grammars and Regular Expressions 2.1 Tree Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Regularity and Recognizabilty . . . . . . . . . . . . . . 2.2 Regular Expressions. Kleene’s Theorem for Tree Languages . . 2.2.1 Substitution and Iteration . . . . . . . . . . . . . . . . . 2.2.2 Regular Expressions and Regular Tree Languages . . . . 2.3 Regular Equations . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Context-free Wo