Tree Automata Techniques and Applications

The two first chapters contain the basics on Tree Automata theory for finite ordered ranked trees. Chapter 3 shows connections between Logic and Tree Automata. Chapter 4 presents Automata with Constraints. Chapter 5 presents Automata for Sets of Tree Languages. Chapter 6 gives the basics on Tree Transducers. Chapter 7 presents Alternating Tree Automata. Chapter 8 is about automata for unranked trees.


Our goal is to fill in the existing gap and to provide a textbook which presents the basics of tree automata and several variants of tree automata which have been devised for applications in the aforementioned domains. We shall discuss only finite tree automata, and the reader interested in infinite trees should consult any recent survey on automata on infinite objects and their applications.

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.

Table of Contents

  • Recognizable Tree Languages and Finite Tree Automata:
  • Regular Grammars and Regular Expressions
  • Logic, Automata and Relations
  • Automata with Constraints
  • Tree Set Automata
  • Tree Transducers
  • Alternating Tree Automata
  • Automata for Unranked Trees

Book Details

Author(s): Hubert Comon, Max Dauchet, R´emi Gilleron, Florent Jacquemard, Denis Lugiez, Christof L¨oding, Sophie Tison and Marc Tommasi.
Format(s): PDF, HTML
File size: 2.0 MB
Number of pages: 262
Link: Download or read online.

Leave a Reply