Formal Tree Series

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