Skip to Main content Skip to Navigation
Journal articles

A finite state version of the Kraft-McMillan theorem

Abstract : 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
Document type :
Journal articles
Complete list of metadata
Contributor : Marie-Pierre Béal Connect in order to contact the contributor
Submitted on : Tuesday, September 6, 2011 - 10:47:46 AM
Last modification on : Wednesday, January 19, 2022 - 4:42:04 PM
Long-term archiving on: : Wednesday, December 7, 2011 - 2:31:02 AM


Files produced by the author(s)


  • HAL Id : hal-00619334, version 1


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



Les métriques sont temporairement indisponibles