Super-State Automata and Rational trees

摘要

We introduce the notion of super-state automata ocnstructed from other automata. This construction i used to solve an open question about enumerative sequences in ratioal trees. We prove that any IN-rational sequene s=(s sub n)>0 of nonnegative integers satisfying the Kraft inequality sigma n >0 s sub n K sup -n less than or equal to 1 is the enumerative sequence of leaves by height of a k-ary rational tree. This result had bee nconjectured and was known only in the case of strict inequality. We also give a new proof of a result about enumerative sequences of nodes in k-ary rational trees.