Codes et motifs. (Codes and motifs). (French) Zbl 0689.68102

We prove, for two codes X and Y, the equivalence of the equality \(XY=YX\) and the existence of two positive integers i and j such that \(X^ i=Y^ j\). Moreover, if one of them is singular, these two conditions are equivalent to the existence of a code Z such that X and Y are powers of Z. Then, we show for each non empty language L commuting with a prefix or circular code X, the existence of a code Y, an integer j and \(I\subset {\mathbb{N}}\) such that \(L=\cup_{i\in I}Y^ i\) and \(X=Y^ j.\)
In particular, if X is a circular code then \(j=1\) and if L is a code, L is a power of X.


68Q45 Formal languages and automata


prefix codes
Full Text: DOI EuDML


[1] 1. J. M. AUTEBERT, L. BOASSON et M. LATTEUX, Motifs et bases de langages (à paraître). Zbl0689.68098 · Zbl 0689.68098
[2] 2. J. BERSTEL et D. PERRIN, Theory of Codes, Academic Press, NewYork, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[3] 3. P. M. COHN, Free Rings and their Relation, Academic Press, NewYork, 1971. Zbl0232.16003 MR371938 · Zbl 0232.16003
[4] 4. G. LALLEMENT, Semigroups and Combinatorial Applications, Wiley, New York, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[5] 5. F. W. LEVI, On semigroups, Bull Calcutta Math. Soc., vol. 36, 1944, p.141-146. Zbl0061.02405 MR11694 · Zbl 0061.02405
[6] 6. M. LOTHAIRE, Combinatorics on Words, Reading, Massachussetts, Addison-Wesley, 1983. Zbl0514.20045 MR675953 · Zbl 0514.20045
[7] 7. R. C. LYNDON et M. P. SCHUTZENBERGER, The équation aM = bN cP in a Free Group, Michigan Math. J., vol. 9, 1962, p. 289-298. Zbl0106.02204 MR162838 · Zbl 0106.02204
[8] 8. M. NIVAT, Éléments de la théorie générale des codes, Automata Theory, E. R.Caianiello éd., p.279-294, Academic Press, NewYork, 1966. Zbl0208.45101 MR241168 · Zbl 0208.45101
[9] 9. D. PERRIN, Codes conjugués, Information and Control, vol. 20, 1972, p. 222-231. Zbl0254.94015 MR345711 · Zbl 0254.94015
[10] 10. H. J. SHYR, Free Monoids and Languages, Lecture Notes, Department of Mathematics, Soochow University, Taipei, Taiwan, R.O.C., 1979. Zbl0407.68076 MR1090325 · Zbl 0407.68076
[11] 11. D. WOOD, A Factor Theorem for Subsets of a Free Monoids, Information and Control, vol. 21, n^\circ 1, 1972, p. 21-26. Zbl0247.68024 MR322085 · Zbl 0247.68024
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.