On constructing minimal deterministic finite automaton recognizing a~prefix-code of a~given cardinality
Prikladnaâ diskretnaâ matematika, no. 2 (2010), pp. 104-116
Voir la notice de l'article provenant de la source Math-Net.Ru
The article considers constructing minimal deterministic finite automaton recognizing a prefix-code of a given cardinality over the alphabet $\{0,1\}$. The considered problem is proved to be equivalent to the problem of finding the shortest addition-chain ending with a given number. Several interesting properties of the desired minimal finite automaton are proved, and the identical problem concerning Moore automata is discussed.
Keywords:
prefix code, finite-state machine, Moore automaton, addition chain.
@article{PDM_2010_2_a10,
author = {I. R. Akishev and M. E. Dvorkin},
title = {On constructing minimal deterministic finite automaton recognizing a~prefix-code of a~given cardinality},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {104--116},
publisher = {mathdoc},
number = {2},
year = {2010},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2010_2_a10/}
}
TY - JOUR AU - I. R. Akishev AU - M. E. Dvorkin TI - On constructing minimal deterministic finite automaton recognizing a~prefix-code of a~given cardinality JO - Prikladnaâ diskretnaâ matematika PY - 2010 SP - 104 EP - 116 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/PDM_2010_2_a10/ LA - ru ID - PDM_2010_2_a10 ER -
%0 Journal Article %A I. R. Akishev %A M. E. Dvorkin %T On constructing minimal deterministic finite automaton recognizing a~prefix-code of a~given cardinality %J Prikladnaâ diskretnaâ matematika %D 2010 %P 104-116 %N 2 %I mathdoc %U http://geodesic.mathdoc.fr/item/PDM_2010_2_a10/ %G ru %F PDM_2010_2_a10
I. R. Akishev; M. E. Dvorkin. On constructing minimal deterministic finite automaton recognizing a~prefix-code of a~given cardinality. Prikladnaâ diskretnaâ matematika, no. 2 (2010), pp. 104-116. http://geodesic.mathdoc.fr/item/PDM_2010_2_a10/