Formal Tree Series

Zoltán Ésik, Werner Kuich

Abstract


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

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v9i21.21737
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the State and University Library and Aarhus University Library