Given an arbitrary submonoid M of the free monoid A*, and given a subset X of M, X is weakly M-complete if any word of M is a factor of some word in X*. The submonoid X* itself is weakly M-dense. We apply two results from [8,9] for obtaining a new characterization of the existence of a finite weakly M-complete prefix set: such a set exists iff M itself is weakly dense in its right unitary hull. This leads to an efficient algorithmic for deciding whether a given finite prefix subset of a finitely generated submonoid M is (weakly) M-complete.
Publié le : 2004-03-04
Classification:
Free monoid,
Submonoid,
Unitary,
Codes,
Prefix,
Suffix,
Bifix,
Complete,
Dense,
Maximal,
[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL],
[INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT],
[MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT]
@article{hal-00461875,
author = {Selmi, Carla and N\'eraud, Jean},
title = {A characterization of complete finite prefix codes in an arbitrary submonoid of A},
journal = {HAL},
volume = {2004},
number = {0},
year = {2004},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00461875}
}
Selmi, Carla; Néraud, Jean. A characterization of complete finite prefix codes in an arbitrary submonoid of A. HAL, Tome 2004 (2004) no. 0, . http://gdmltest.u-ga.fr/item/hal-00461875/