On Primitive Words With Non-Primitive Product
RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 4

Let 𝒜 be an alphabet of size n ≥ 2. Our goal in this paper is to give a complete description of primitive words p≠q over 𝒜 such that pq is non-primitive. As an application, we will count the cardinality of the set ℰ(l,𝒜) of all couples (p, q) of distinct primitive words such that |p| = |q| = l and pq is non-primitive, where l is a positive integer. Then we give a combinatorial formula for the cardinality ε(n, l) of this set. The density in {(p, q) : p, q are distinct primitive words and |p| = |q| = l} of the set ℰ(l,𝒜) is also discussed.

DOI : 10.1051/ita/2022004
Classification : 68R15, 68Q45
Keywords: Combinatorics on words, Primitive words, primitive root, Möbius inversion formula 
@article{ITA_2022__56_1_A4_0,
     author = {Echi, Othman and Khalfallah, Adel and Kroumi, Dhaker},
     title = {On {Primitive} {Words} {With} {Non-Primitive} {Product}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     doi = {10.1051/ita/2022004},
     mrnumber = {4382750},
     zbl = {1497.68402},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2022004/}
}
TY  - JOUR
AU  - Echi, Othman
AU  - Khalfallah, Adel
AU  - Kroumi, Dhaker
TI  - On Primitive Words With Non-Primitive Product
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2022
VL  - 56
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2022004/
DO  - 10.1051/ita/2022004
LA  - en
ID  - ITA_2022__56_1_A4_0
ER  - 
%0 Journal Article
%A Echi, Othman
%A Khalfallah, Adel
%A Kroumi, Dhaker
%T On Primitive Words With Non-Primitive Product
%J RAIRO. Theoretical Informatics and Applications
%D 2022
%V 56
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2022004/
%R 10.1051/ita/2022004
%G en
%F ITA_2022__56_1_A4_0
Echi, Othman; Khalfallah, Adel; Kroumi, Dhaker. On Primitive Words With Non-Primitive Product. RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 4. doi: 10.1051/ita/2022004

[1] G. Castiglione, G. Fici and A. Restivo, Primitive sets of words. Theoret. Comput. Sci. 866 (2021) 25–36. | MR | Zbl | DOI

[2] C. Choffrut and J. Karhumaki, Combinatorics of words, in Vol. 1 of Handbook of Formal Languages. Springer-Verlag, Berlin, Heidelberg (1997) 329–438. | MR | DOI

[3] C. Chunhua, Y. Shuang and D. Yang, Some kinds of primitive and non-primitive words. Acta Inform. 51 (2014) 339–346. | MR | Zbl | DOI

[4] P. Dömösi, S. Horväth and M. Ito, Formal languages and primitive words. Publ. Math. Debrecen 42 (1993) 315–321. | MR | Zbl | DOI

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

[6] 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

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

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

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

[10] O. Echi, Non-primitive words of the form p q m . RAIRO-Theor. Inf. Appl. 51 (2017) 135–139. | MR | Zbl | DOI

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

[12] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 6th edn. Oxford University Press, Oxford (2008). | MR | Zbl | DOI

[13] S. Horváth, Strong interchangeability and nonlinearity of primitive words, in: Algebraic Methods in Language Processing. Univ. of Twente, Enschede, The Netherlands (1995) 173–178.

[14] A. Lentin and M. P. Schützenberger, A combinatorial problem in the theory of free monoids. In: Combinatorial Mathematics and its Applications. Proc. Conf., Univ. North Carolina, Chapel Hill, N.C. (1967) 128–144. | MR | Zbl

[15] M. Lothaire, Combinatorics on Words. Addison-Wesley (1983). | MR | Zbl

[16] R. C. Lyndon and M. P. Schützenberger, The equation a M = b N c P in a free group.Mich. Math. J.9 (1962) 289–298. | MR | Zbl | DOI

[17] A. Restivo, On a question of McNaughton and Papert. Inf. Control 25 (1974) 93–101. | MR | Zbl | DOI

[18] C. Reis and H. J. Shyr, Some properties of disjunctive languages on a free monoid. Inf. Control 37 (1978) 334–344. | MR | Zbl | DOI

[19] R. Sińya, Asymptotic Approximation by Regular Languages. In: theory and practice of computer science, SOFSEM 2021, LNCS vol 12607 (2021) 74–88. | MR | Zbl

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

[21] H. J. Shyr, Free monoids and languages. 2nd edition. Lecture notes, Hon Min Book Co., Taichung (1991). | MR | Zbl

[22] H. J. Shyr and F. K. Tu, Local distribution of non-primitive words. In: Ordered structures and algebra of computer languages. World Scientific, River Edge, NJ (1993) 202–217. | Zbl

Cité par Sources :