A Kleene Theorem for Weighted Tree Automata

摘要

In this paper we prove Kleene's result for formal tree series over a commutative semiring A (which is not necessarily complete or continuous or idem-potent), i.e., the class of formal tree series over A which are accepted by weighted tree automata, and the class of rational tree series over A are equal. We show the result by direct automata-theoretic constructions and prove their correctness.