Formal languages and automata VII: Formal tree series (Part I)Abstract
This is the seventh paper of a series of papers that will give a survey on several topics on formal languages and automata by using semirings, formal power series, matrices and xed point theory. The seventh paper of this series deals with tree (series) automata and systems of equations over tree. The main topics of the paper are the following. 1. Tree automata (resp. nite, polynomial tree automata), whose behaviors are tree series over a semiring, and systems of equations (resp. nite, polynomial systems of equations), whose least solutions are tuples of tree series over a semiring, are equivalent. 2. A Kleene result: the class of recognizable tree series is characterized by rational tree series expressions.