A finite state version of the Kraft-McMillan theorem

Frédérique Bassino (1) , Marie-Pierre Béal (2) , Dominique Perrin (2)

1 LIPN - Laboratoire d'Informatique de Paris-Nord
2 LIGM - Laboratoire d'Informatique Gaspard-Monge

The main result is a finite-state version of the Kraft-McMillan theorem characterizing the generating sequence of a k-ary regular tree. The proof uses a new contruction called the multiset construction which is a version with multiplicities of the well-known subset construction of automata theory

Domaines: Algorithme et structure de données [cs.DS]

Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin. A finite state version of the Kraft-McMillan theorem. SIAM Journal on Computing, 2000, 30 (4), pp.1211-1230. ⟨hal-00619334⟩