On Morphisms Preserving Palindromic Richness

• Autorzy: Dolce Francesco , Pelantová Edita

Identyfikatory

DOI

10.3233/FI-222102

• Języki publikacji: EN

Abstrakty

EN

It is known that each word of length n contains at most n + 1 distinct palindromes. A finite rich word is a word with maximal number of palindromic factors. The definition of palindromic richness can be naturally extended to infinite words. Sturmian words and Rote complementary symmetric sequences form two classes of binary rich words, while episturmian words and words coding symmetric d-interval exchange transformations give us other examples on larger alphabets. In this paper we look for morphisms of the free monoid, which allow us to construct new rich words from already known rich words. We focus on morphisms in Class Pret. This class contains morphisms injective on the alphabet and satisfying a particular palindromicity property: for every morphism ϕ in the class there exists a palindrome w such that ϕ(a)w is a first complete return word to w for each letter a. We characterize Pret morphisms which preserve richness over a binary alphabet. We also study marked Pret morphisms acting on alphabets with more letters. In particular we show that every Arnoux-Rauzy morphism is conjugated to a morphism in Class Pret and that it preserves richness.

Słowa kluczowe

EN

Palindromic richness; morphisms; bispecial factors; Class Pret; Class P

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 1
• Strony: 1--25
• Opis fizyczny: Bibliogr. 36 poz.

Twórcy

autor

Dolce Francesco

• Czech Technical University in Prague, 160 00 Prague 6 - Dejvice, Czech Republic.

autor

Pelantová Edita

• Czech Technical University in Prague, 160 00 Prague 6 - Dejvice, Czech Republic.

Bibliografia

• [1] Arnoux P, Rauzy G. Représentation géométrique de suites de complexité 2n + 1, Bulletin de la Société Mathématique de France, 1991. 119(2):199-215. doi.org/10.24033/bsmf.2164.
• [2] L. Balková, E. Pelantová, Š. Starosta, Palindromes in infinite ternary words, RAIRO - Theoretical Informatics and Applications, 2009. 43(4):687-702. doi:10.1051/ita/2009016.
• [3] Balková L., Pelantová E, Starosta Š. Sturmian Jungle (or Garden?) on Multiliteral Alphabets, RAIRO -Theoretical Informatics and Applications, 2010. 44(4):443-470. doi:10.1051/ita/2011002.
• [4] Balková L., Pelantová E, Starosta Š. Infinite Words with Finite Defect, Advances in Applied Mathematics, 2011. 47(3):562-574. doi:10.1016/j.aam.2010.11.006.
• [5] Baranwal AR. Decision Algorithms for Ostrowski-Automatic Sequences, Master Thesis, University of Waterloo (2020). ID: 229124363.
• [6] Baranwal AR, Shallit J. Repetitions in infinite palindrome-rich words, in: R. Mercas and D. Reidenbach (eds.), Proceedings WORDS 2019, Lecture Notes in Computer Science, vol. 11682, Springer, 2019 pp. 93-105. doi:10.1007/978-3-030-28796-2_7.
• [7] Berthé V, De Felice C, Dolce F, Leroy J, Perrin D, Reutenauer C, Rindone G. Acyclic, connected and tree sets, Monatshefte für Mathematik, 2015. 176:521-550. doi:10.1007/s00605-014-0721-4.
• [8] Berthé V, De Felice C, Dolce F, Leroy J, Perrin D, Reutenauer C, Rindone G. Maximal bifix decoding, Discrete Mathematics, 2015. 338(5):725-742. doi:10.1016/j.disc.2014.12.010.
• [9] Berthé V, De Felice C, Delecroix V, Dolce F, Leroy J, Perrin D, Reutenauer C, Rindone G. Specular sets, Theoretical Computer Science, 2017. 684:3-28. doi:10.1016/j.tcs.2017.03.001.
• [10] Blondin Massé A, Brlek S, Labbé S, Vuillon L. Palindromic complexity of codings of rotations, Theoretical Computer Science, 2011. 412(46):6455-6463. doi:10.1016/j.tcs.2011.08.007.
• [11] Brlek S, Hamel S, Nivat M, Reutenauer C. On the palindromic complexity of infinite words, in: J. Berstel, J. Karhumäki,D. Perrin (Eds.), Combinatorics on Words with Applications, International Journal of Foundations of Computer Science, 2004. 15(2):293-306. doi:10.1142/S012905410400242X.
• [12] Bucci M, De Luca A, Glen A, Zamboni LQ. A connection between palindromic and factor complexity using return words, Advances in Applied Mathematics. 2009. 42(1):60-74. doi:10.1016/j.aam.2008.03.005.
• [13] Cassaigne J. An algorithm to test if a given circular HD0L-language avoids a pattern, in: IFIP World Computer Congress’94, Elsevier, 1994. pp. 459-464. ID:1744066124 F. Dolce and E. Pelantová / On Morphisms Preserving Palindromic Richness
• [14] Currie JD, Mol L, Rampersad N. The repetition threshold for binary rich words, Discrete Mathematics & Theoretical Computer Science, 2020. vol. 22 no 1. doi:10.23638/DMTCS-22-1-6.
• [15] Droubay X, Justin J, Pirillo G. Episturmian words and some constructions of de Luca and Rauzy, Theoretical Computer Science, 2001. 255(1-2):539-553. doi:10.1016/S0304-3975(99)00320-5.
• [16] Durand F. A generalization of Cobham Theorem, Theory of Computing Systems, 1998. 31:169-185. Id:hal-00303322.
• [17] Durand F. A characterization of substitutive sequences using return words, Discrete Mathematics, 1998. 179(1-3):89-101. doi:10.1016/S0012-365X(97)00029-0.
• [18] Frid A. Applying a uniform marked morphism to a word, Discrete Mathematics and Theoretical Computer Science, 1999. 3(3):125-139. doi:10.46298/dmtcs.255.
• [19] Frid A, Puzynina S, Zamboni LQ. On palindromic factorization of words, Advances in Applied Mathematics, 2013. 50(5) 737-748. doi:10.1016/j.aam.2013.01.002.
• [20] Glen A, Justin J. Episturmian words: a survey, RAIRO - Theoretical Informatics and Applications, 2009.43(3)403-442. doi:10.1051/ita/2009003.
• [21] Glen A, Justin J, Widmer S, Zamboni LQ. Palindromic richness, European Journal of Combinatorics, 2009. 30(2):510-531. doi:10.1016/j.ejc.2008.04.006.
• [22] Guo C, Shallit J, Shur AM. Palindromic rich words and run-length encodings, Information Processing Letters, 2016. 116(12):735-738. doi:10.1016/j.ipl.2016.07.001.
• [23] Harju T, Vesti J, Zamboni LQ. On a question of Hof, Knill and Simon on palindromic substitutive systems, Monatshefte für Mathematik, 2016. 179:379-388. Id: hal-01829318.
• [24] Hof A, Knill O, Simon B. Singular continuous spectrum for palindromic Schrödinger operators, Communications in mathematical physics, 1995. 174(1):149-159. doi:10.1007/BF02099468.
• [25] Justin J, Pirillo G. Episturmian words and episturmian morphisms, Theoretical Computer Science, 2002. 276(1-2):281-313. doi:10.1016/S0304-3975(01)00207-9.
• [26] Klouda K. Bispecial factors in circular non-pushy D0L languages, Theoretical Computer Science, 2012. 445(3):63-74. doi:10.1016/j.tcs.2012.05.007.
• [27] Labbé S, Pelantová E. Palindromic sequences generated from marked morphisms, European Journal of Combinatorics, 2016. 51:200-214. doi:10.1016/j.ejc.2015.05.006.
• [28] Meyer CD. Matrix Analysis and Applied Linear Algebra, SIAM, 2000. ISBN-13:978-0898714548, 10:0898714540.
• [29] Lothaire M. Algebraic Combinatorics on Words, Cambridge University Press, 2002. ISBN-13:978-0521180719, 10:0521180716.
• [30] Medková K, Pelantová E, Vuillon L. Derived sequences of complementary symmetric Rote sequences, RAIRO - Theoretical Informatics and Applications, 2019. 53(3-4):125-151. doi:10.1051/ita/2019004.
• [31] Pelantová E, Starosta Š. On Words with the Zero Palindromic Defect, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds), Combinatorics on Words. WORDS 2017, Lecture Notes in Computer Science, vol. 10432. Springer, Cham, 2017. doi:10.1007/978-3-319-66396-8_7.
• [32] Pytheas Fogg N. Substitutions in dynamics, arithmetics and combinatorics, volume 1794 of Lecture Notes in Mathematics. Springer-Verlag (2002). Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. ISBN-13:978-3540441410, 10:3540441417.
• [33] Rubinchik M, Shur AM. EERTREE: An efficient data structure for processing palindromes in strings, European J. Combin., 2018. 68:249-265. doi:10.1016/j.ejc.2017.07.021.
• [34] Rukavicka J. On the number of Rich Words, In E. Charlier, J. Leroy, M. Rigo (Eds), DLT 2017, Lecture Notes in Computer Science, vol 10396, Springer (2017), 345-352.
• [35] Starosta Š. Morphic images of episturmian words having finite palindromic defect, European Journal of Combinatorics, 2016. 51:359-371.
• [36] Vesti J. Extensions of rich words, Theoretical Computer Science, 2014. 548(4): 14-24. doi:10.1016/j.tcs.2014.06.033.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)