The Number of Distinct Subpalindromes in Random Words

• Autorzy: Rubinchik M. , Shur A. M.

Identyfikatory

DOI

10.3233/FI-2016-1366

• Języki publikacji: EN

Abstrakty

EN

We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation,Θ(√n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit lim_n→∞ E(n, k)=√n does not exist for any κ ≥ 2, lim inf_n→∞ E(n; k)=√n =Θ(1), and lim sup_n→∞ E(n; k)=√n = Θ(√k). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.

Słowa kluczowe

EN

palindrome; alphabet; number theory; machine theory; data structures

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 371--384
• Opis fizyczny: Bibliogr. 11 poz., tab., wykr.

Twórcy

autor

Rubinchik M.

• Ural Federal University Ekaterinburg, Russia

autor

Shur A. M.

• Ural Federal University Ekaterinburg, Russia

Bibliografia

• [1] Richmond LB, Shallit J. Counting the Palstars. Electronic J. Combinatorics. 2014; 21(3) # P3.25.
• [2] Fici G, Zamboni L. On the least number of palindromes contained in an infinite word. Theoret. Comput. Sci. 2013; 481:1–8. doi: 10.1016/j.tcs.2013.02.013.
• [3] Droubay X, Justin J, Pirillo G. Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 2001; 255:539–553. doi: 10.1016/S0304-3975(99)00320-5.
• [4] Glen A, Justin J, Widmer S, Zamboni L. Palindromic richness. European J. Combinatorics. 2009; 30(2):510–531. doi: 10.1016/j.ejc.2008.04.006.
• [5] Guo C, Shallit J, Shur AM. On the combinatorics of palindromes and antipalindromes. arXiv:1503.09112 [cs.FL]; 2015.
• [6] Anisiu MC, Anisiu V, Kása Z. Total palindrome complexity of finite words. Discrete Math. 2010; 310:109–114. doi: 10.1016/j.disc.2009.08.002.
• [7] Guibas LJ, Odlyzko AM. Maximal prefix-synchronized codes. SIAM J. Applied Math. 1978; 35:401–418. Available from: http://www.jstor.org/stable/2100678.
• [8] Guibas LJ, Odlyzko AM. String overlaps, pattern matching, and nontransitive games. J. Combin. Theory. Ser. A. 1981; 30:183–208.
• [9] Groult R, Prieur E, Richomme G. Counting distinct palindromes in a word in linear time. Inform. Process. Lett. 2010; 110:908–912. doi: 10.1016/j.ipl.2010.07.018.
• [10] Kosolobov D, Rubinchik M, Shur AM. Finding distinct subpalindromes online. Proc. Prague Stringology Conference. PSC 2013, Czech Technical University in Prague; 2013. ISBN- 978-80-01-05330-0.
• [11] Lothaire M. Combinatorics onWords. vol. 17 of Encyclopedia of Mathematics and Its Applications, Addison-Wesley; 1983. ISBN- 10:0201135167, 13:9780201135169.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).