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 metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619334
Contributor : Marie-Pierre Béal <>
Submitted on : Tuesday, September 6, 2011 - 10:47:46 AM
Last modification on : Thursday, February 7, 2019 - 5:49:10 PM
Long-term archiving on : Wednesday, December 7, 2011 - 2:31:02 AM

Files

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619334, version 1

Citation

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⟩

Share

Metrics

Record views

356

Files downloads

246