A finite state version of the Kraft-McMillan theorem

Authors
Bassino, F Beal, MP Perrin, D
Citation
F. Bassino et al., A finite state version of the Kraft-McMillan theorem, SIAM J COMP, 30(4), 2000, pp. 1211-1230
Citations number
19
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
30
Issue
4
Year of publication
2000
Pages
1211 - 1230
Database
ISI
SICI code
0097-5397(20001012)30:4<1211:AFSVOT>2.0.ZU;2-U
Abstract
The main result is a finite-state version of the Kraft McMillan theorem cha racterizing the generating sequence of a k-ary regular tree. The proof uses a new construction called the multiset construction, which is a version wi th multiplicities of the well-known subset construction of automata theory.