Tata: the book

• A full version (October, 12th 2007) is available. BibteX entry .
• and of course errata associated with this version.
• Acknowledgments:

  Many people gave substantial suggestions to improve the contents of this book. These are, in alphabetic order, Witold Charatonik, Zoltan Fülöp, Werner Kuich, Markus Lohrey, Jun Matsuda, Aart Middeldorp, Hitoshi Ohsaki, P. K. Manivannan, Masahiko Sakai, Helmut Seidl, Stephan Tobies, Ralf Treinen, Thomas Uribe, Sandor Vágvölgyi, Kumar N. Verma, Toshiyuki Yamada.

  The book is still under construction. We seek for comments and suggestions. Please write to: tata-discuss@lists.gforge.inria.fr

Tata: how to

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.

• Contents of the chapters
  • Chapter 1 - Recognizable Tree Languages and Finite Tree Automata:
  • Chapter 2 - Regular Grammars and Regular Expressions
  • Chapter 3 - Logic, Automata and Relations
  • Chapter 4 - Automata with Constraints
  • Chapter 5 - Tree Set Automata
  • Chapter 6 - Tree Transducers
  • Chapter 7 - Alternating Tree Automata
  • Chapter 8 - Automata for Unranked Trees

Tata: the future

We know that the book currently covers only few aspects of tree automata. A new chapter covering Automata for unordered trees and more generally tree automata for trees modulo equational theories is scheduled. We welcome submissions of additional chapters investigating other aspects of tree automata. We believe it is important to keep the homogeneity of the book, which should not be a collection of chapters. Hence submissions should be consistent with previous chapters. They will be reviewed by the current authors. If you wish to contribute, please send a message to tata-discuss@lists.gforge.inria.fr.

Tata : the authors

Hubert Comon	Max Dauchet	Remi Gilleron
Florent Jacquemard	Denis Lugiez	Christof Löding
Sophie Tison	Marc Tommasi

Some related links

Libraries, tools

• TIMBUK is is a Library of Objective Caml functions designed to manipulate Tree Automata. Developped under GPL by Thomas Genet and Valérie Viet Triem Tong.
• RX : an interpreter for Rational Tree Languages, by Johannes Waldmann at Leipzig university.
• MONA/FIDO: a system based on Weak Second-order Theory of One or Two succesors developed at BRICS, by Nils Klarlund, Anders Møller and Michael I. Schwartzbach
• Elan now provides a library for tree automata manipulations. Elan is a software developped by Loria (CNRS, INRIA, Universities of Nancy).
• Autowrite implements the tree automata constructions used in the decidability proofs of the call-by-need properties and many useful operations on terms, TRSs and tree automata. Autowrite is developped by I. Durand.