Non-primitive words of the form $\bold{p}\bold{q}^{\bold{m}}$

Echi, Othman

doi:10.1051/ita/2017012

Non-primitive words of the form

𝐩 𝐪^{𝐦}

Echi, Othman ^1,²

¹ King Fahd University of Petroleum and Minerals, Department of Mathematics and Statistics PO Box 5046, Dhahran 31261, Saudi Arabia.
² University Tunis-El Manar. Faculty of Sciences of Tunis, Department of Mathematics, 2092 Tunis, Tunisia.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 3, pp. 141-166

Résumé

Let $p, q$ be two distinct primitive words. According to Lentin−Schützenberger [9], the language $p^{+} q^{+}$ contains at most one non-primitive word and if $p q^{m}$ is not primitive, then $m \leq \frac{2 ∣ p ∣}{∣ q ∣} + 3$ . In this paper we give a sharper upper bound, namely, $m \leq ⌊ \frac{∣ p ∣ - 2}{∣ q ∣} + 2 ⌋,$ where $⌊ x ⌋$ stands for the floor of $x$ .

Reçu le : 2017-11-08
Accepté le : 2017-11-14

DOI : 10.1051/ita/2017012

Classification : 68R15
Keywords: Combinatorics on words, primitive word, primitive root

Affiliations des auteurs :

Echi, Othman ^{1, 2}

¹ King Fahd University of Petroleum and Minerals, Department of Mathematics and Statistics PO Box 5046, Dhahran 31261, Saudi Arabia.
² University Tunis-El Manar. Faculty of Sciences of Tunis, Department of Mathematics, 2092 Tunis, Tunisia.

@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},
     year = {2017},
     publisher = {EDP Sciences},
     volume = {51},
     number = {3},
     doi = {10.1051/ita/2017012},
     language = {en},
     url = {https://www.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  - https://www.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 https://www.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

Bibliographie
Cité par

C. Chunhua, Y. Shuang and Y. Di, Some Kinds of Primitive and non-primitive Words. Acta Inform. 51 (2014) 339–346. | Zbl | MR | DOI

P. Dömösi and G. Horváth, Alternative proof of the Lyndon−Schützenberger theorem. Theoret. Comput. Sci. 366 (2006) 194–198. | Zbl | MR | DOI

P. Dömösi and G. Horvath, The language of primitive words is not regular: two simple proofs. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 87 (2005) 191–197. | Zbl | MR

P. Dömösi, G. Horváth and L. Vuillon, On the Shyr−Yu theorem. Theoret. Comput. Sci. 410 (2009) 4874–4877. | Zbl | MR | DOI

P. Dömösi and M. Ito, Context-free languages and primitive words. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ (2015). | MR | Zbl

P. Dömösi, M. Ito and S. Marcus, Marcus contextual languages consisting of primitive words. Discrete Math. 308 (2008) 4877–4881. | Zbl | MR | DOI

O. Echi and M. Naimi, Primitive words and spectral spaces. New York J. Math. 14 (2008) 719–731. | Zbl | MR

N.J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. | Zbl | MR | DOI

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

R.C. Lyndon and M.P. Schützenberger, The equation $a^{M} = b^{N} c^{P}$ in a free group. Michigan Math. J. 9 (1962) 289–98. | MR | Zbl | DOI

H.J. Shyr and S.S. Yu, Non-primitive words in the language $p^{+} q^{+}$ . Soochow J. Math. 20 (1994) 535–546. | Zbl | MR

Cité par Sources :