Talk abstract:

A Finite State Version of the Kraft-McMillan Theorem

Marie-Pierre Béal
Universite do Marne-la-Vallee
beal@monge.univ-mlv.fr
http://www-igm.univ-mlv.fr/~beal

Joint work with Fréderique Bassino and Dominique Perrin.

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) _{n 0} of nonnegative integers satisfying the Kraft inequality _{n 0}s_nk^-n 1 is the enumerative sequence of leaves by height of a k-ary rational tree. This result is a finite state version of the Kraft-McMillan theorem. We then use it to completely characterize the series that are the enumerative sequences of nodes in a k-ary rational tree.

Material used during the talk

Back to Workshop Schedule

Back to Codes, Systems and Graphical Models