Séminaire Lotharingien de Combinatoire, B18h (1987).
[Formerly: Publ. I.R.M.A. Strasbourg, 1988, 358/S-18, p. 136-137.]

Véronique Bruyère

Factorization of prefix-closed subsets of words

Abstract. A set of words is prefix-closed if it contains the beginning of each word. We exhibit examples of unambiguous factorizations (into two sets) of such finite sets. These factorizations are completely described here for two particular families. First, a bijection between finite maximal prefix codes and prefix-closed sets allows one to translate the composition of codes into a factorization of prefix-closed sets. Then a second family is studied, whose examples (due to D. Perrin ) involve asynchronous codes.

The paper has been finally published under the title "Factorisation des ensembles préfixiels" in RAIRO Inform. Théor. Appl. 23 (1989), 295-315.