Kleene-Type Results for Weighted Tree-Automata
Christian Pech · Qucosa (Saxon State and University Library Dresden) · 2003
The main result of this thesis is the generalization of the Kleene-theorem to formal tree-series over commutative semirings (the Kleene theorem states the coincidence between rational and recognizable formal languages). To this end weighted tree-languages are introduced and the Kleene-theorem is proved for them. The desired result for formal tree-series is then obtained through application of a homomorphism that relates weighted tree-languages with formal tree-series. In the second part of the thesis the connections to the theorie of Iteration-theories are discovered. In particular it is shown there that the grove-theory of formal tree-series forms a partial iteration-theory.