Locally complete sets and finite decomposable codes
Selmi, Carla ; Néraud, Jean
HAL, hal-00460321 / Harvested from HAL
We are interested in the concept of locally complete set : A subset X of the free monoid is locally complete if a code Y in A* exists, with Y different from A, X* included in Y* and both the sets X* and Y* have the same sets of factors. Our contribution is based on the three following results: A characterization of local completeness for every thin set in terms of morphic images. A polynomial time algorithm for deciding whether a finite code is locally complete. A polynomial time algorithm for deciding whether a finite maximal code is decomposable.
Publié le : 2002-02-26
Classification:  Free monoid,  Interpretation,  Uncompletable word,  Code,  Thin set,  Maximal code,  Complete set,  Bernoulli distribution Decomposable code,  [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-00460321,
     author = {Selmi, Carla and N\'eraud, Jean},
     title = {Locally complete sets and finite decomposable codes},
     journal = {HAL},
     volume = {2002},
     number = {0},
     year = {2002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00460321}
}
Selmi, Carla; Néraud, Jean. Locally complete sets and finite decomposable codes. HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/hal-00460321/