Let be two distinct primitive words. According to Lentin−Schützenberger [9], the language contains at most one non-primitive word and if is not primitive, then . In this paper we give a sharper upper bound, namely, where stands for the floor of .
Accepté le :
Mots-clés : Combinatorics on words, primitive word, primitive root
@article{ITA_2017__51_3_141_0, author = {Echi, Othman}, title = {Non-primitive words of the form $\bold{p}\bold{q}^{\bold{m}}$}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {141--166}, publisher = {EDP-Sciences}, volume = {51}, number = {3}, year = {2017}, doi = {10.1051/ita/2017012}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2017012/} }
TY - JOUR AU - Echi, Othman TI - Non-primitive words of the form $\bold{p}\bold{q}^{\bold{m}}$ JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2017 SP - 141 EP - 166 VL - 51 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2017012/ DO - 10.1051/ita/2017012 LA - en ID - ITA_2017__51_3_141_0 ER -
%0 Journal Article %A Echi, Othman %T Non-primitive words of the form $\bold{p}\bold{q}^{\bold{m}}$ %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2017 %P 141-166 %V 51 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2017012/ %R 10.1051/ita/2017012 %G en %F ITA_2017__51_3_141_0
Echi, Othman. Non-primitive words of the form $\bold{p}\bold{q}^{\bold{m}}$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 3, pp. 141-166. doi : 10.1051/ita/2017012. http://archive.numdam.org/articles/10.1051/ita/2017012/
Some Kinds of Primitive and non-primitive Words. Acta Inform. 51 (2014) 339–346. | DOI | MR | Zbl
, and ,Alternative proof of the Lyndon−Schützenberger theorem. Theoret. Comput. Sci. 366 (2006) 194–198. | DOI | MR | Zbl
and ,The language of primitive words is not regular: two simple proofs. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 87 (2005) 191–197. | MR | Zbl
and ,On the Shyr−Yu theorem. Theoret. Comput. Sci. 410 (2009) 4874–4877. | DOI | MR | Zbl
, and ,P. Dömösi and M. Ito, Context-free languages and primitive words. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ (2015). | MR | Zbl
Marcus contextual languages consisting of primitive words. Discrete Math. 308 (2008) 4877–4881. | DOI | MR | Zbl
, and ,Primitive words and spectral spaces. New York J. Math. 14 (2008) 719–731. | MR | Zbl
and ,Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. | DOI | MR | Zbl
and ,A. Lentin and M. P. Schützenberger, A combinatorial problem in the theory of free monoids. 1969 Combinatorial Mathematics and its Applications. Proc. Conf., Univ. North Carolina, Chapel Hill, N.C. Univ. North Carolina Press, Chapel Hill, N.C. (1967) 128–144. | MR | Zbl
M. Lothaire, Combinatorics on words (Corrected reprint of the 1983 original). Cambridge University Press, Cambridge (1997). | MR | Zbl
M. Lothaire, Algebraic combinatorics on words. Vol. 90 of Encyclopedia of Math. Appl. Cambridge University Press, Cambridge (2002). | Zbl
The equation in a free group. Michigan Math. J. 9 (1962) 289–98. | DOI | MR | Zbl
and ,Non-primitive words in the language . Soochow J. Math. 20 (1994) 535–546. | MR | Zbl
and ,Cité par Sources :