Super-State Automata and Rational Trees

We introduce the notion of super-state automaton constructed from another automaton. This construction is used to solve an open question about enumerative sequences of leaves of rational trees. We prove that any N-rational sequence s = (s n ) n0 of nonnegative numbers satisfying the Kraft inequality P n0 s n k \Gamman 1 is the enumerative sequence of leaves by height of a k-ary rational tree. This result had been conjectured and was known only in the case of strict inequality. We also give new proofs, based on the notion of super-state automata, to the following known result about enumerative sequences of nodes in trees: any N-rational series t that has a primitive linear representation, such that t 0 = 1, 8n 1; t n kt n\Gamma1 , and whose convergence radius is strictly greater than 1=k, is the enumerative sequence of nodes by height in a k-ary rational tree. 1 Introduction We introduce in this paper the notion of super-state automata, which can informally be stated as follows..