Open AccessFormal Tree Series
Author(s) -
Zoltán Ésik,
Werner Kuich
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i21.21737
Subject(s) - tree (set theory) , mathematics , formal power series , combinatorics , tree automaton , discrete mathematics , automaton , power series , computer science , theoretical computer science , mathematical analysis
In this survey we generalize some results on formal tree languages, tree grammars and tree automata by an algebraic treatment using semirings, fixed point theory, formal tree series and matrices. The use of these mathematical constructs makes definitions, constructions, and proofs more satisfactory from an mathematical point of view than the customary ones. The contents of this survey paper is indicated by the titles of the sections: 1. Introduction 2. Preliminaries 3. Tree automata and systems of equations 4. Closure properties and a Kleene Theorem for recognizable tree series 5. Pushdown tree automata, algebraic tree systems, and a Kleene Theorem 6. Tree series transducers 7. Full abstract families of tree series 8. Connections to formal power series