Codes limites et factorisations finies du monoïde libre. (Limit codes and finite factorizations of free monoids). (French) Zbl 0643.20037

Monoidal factorizations of free monoids are introduced and studied. A totally ordered family \((M_ i)_{i\in I}\) of submonoids of the free monoid \(A^*\) is called a monoidal factorization of \(A^*\) if for every nonempty word w there are nonempty words \(m_ i\in M_{\alpha_ i}\) such that \(w=m_ 1m_ 2...m_ n\) with \(\alpha_ 1<\alpha_ 2<...<\alpha_ n\).
Reviewer: T.J.Harju


20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI EuDML


[1] 1. BERSTEL-PERRIN, Theory of Codes, Academic Press, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[2] 2. BERSTEL-PERRIN, Codes Circulaires, Combinatorics on Words, Progress and Perspectives, Academic Press, 1984. Zbl0563.68063 · Zbl 0563.68063
[3] 3. LOTHAIRE, Combinatorics on Words, Addison-Wesley, 1983. Zbl0514.20045 MR675953 · Zbl 0514.20045
[4] 4. SCHUTZENBERGER, Sur une propriété combinatoire des algèbres de Lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire Dubreuil-Pisot, année 58-59, I.H.P., Paris, 1959.
[5] 5. SCHUTZENBERGER, On a Factorisation of Free Monoids, Proc. Amer. Math. Soc., vol. 16, 1965, p. 21-24. Zbl0219.20039 MR170971 · Zbl 0219.20039
[6] 6. VIENNOT, Algèbres de Lie libres et monoïdes libres, Thèse d’état, Paris-VII, 1974.
[7] 7. VIENNOT, Algèbres de Lie libres et monoïdes libres, Lecture Notes in Math., n^\circ 691, Springer-Verlag, 1978. Zbl0395.17003 MR516004 · Zbl 0395.17003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.