Upper Bound for Palindromic and Factor Complexity of Rich Words

Rukavicka, Josef

RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 1

A finite word $w$ of length $n$ contains at most $n+1$ distinct palindromic factors. If the bound $n+1$ is attained, the word $w$ is called rich. An infinite word $w$ is called rich if every finite factor of $w$ is rich.

Let $w$ be a word (finite or infinite) over an alphabet with $q>1$ letters, let ${\mathrm{Fac}}_w\left(n\right)$ be the set of palindromic factors of length $n$ of the word $w$, and let ${\mathrm{Pal}}_w\left(n\right)⫅{\mathrm{Fac}}_w\left(n\right)$ be the set of palindromic factors of length n of the word $w$.

We present several upper bounds for $|{\mathrm{Fac}}_w\left(n\right)|$ and )| and |Pal$|{\mathrm{Pal}}_w\left(n\right)|$where $w$ is a rich word. Let $\delta =\frac{3}{2(ln3-ln2)}$. In particular we show that $$|{\mathrm{Fac}}_w\left(n\right)|\le {\left(4q^{2}n\right)}^{\delta ln2n+2}$$

In 2007, Baláži, Masáková, and Pelantová showed that

$$|{\mathrm{Pal}}_w\left(n\right)|+|{\mathrm{Pal}}_w(n+1)|\le |{\mathrm{Fac}}_w(n+1)|-|{\mathrm{Fac}}_w\left(n\right)|+2$$

where $w$ is an infinite word whose set of factors is closed under reversal. We prove this inequality for every finite word $\nu$ with $\left|\nu \right|\ge n+1$ and ${\mathrm{Fac}}_{\nu }(n+1)$ closed under reversal.

Classification : 68R15
Keywords: Rich words, Palindromes, Palindromic complexity, Factor complexity

[1] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theor. Comput. Sci. 292 (2003) 9–31. | MR | Zbl | DOI

[2] P. Baláži, Z. Masáková and E. Pelantová, Factor versus palindromic complexity of uniformly recurrent infinite words. Theor. Comput. Sci. 380 (2007) 266–275. | MR | Zbl | DOI

[3] L. Balková, Beta-integers and Quasicrystals, PhD thesis, Czech Technical University in Prague and Université Paris Diderot-Paris 7 (2008).

[4] L. Balková, E. Pelantová and Š. Starosta, Sturmian jungle (or garden?) on multiliteral alphabets. RAIRO: ITA 44 (2010) 443–470. | MR | Zbl | Numdam

[5] A. Blondin Massé, S. Brlek, S. Labbé and L. Vuillon, Palindromic complexity of codings of rotations. Theor. Comput. Sci. 412 (2011) 6455–6463. | MR | Zbl | DOI

[6] M. Bucci, A. De Luca, A. Glen and L. Q. Zamboni, A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009) 60–74. | MR | Zbl | DOI

[7] M. Bucci, A. De Luca, A. Glen and L. Q. Zamboni, A new characteristic property of rich words. Theor. Comput. Sci. 410 (2009) 2860–2863. | MR | Zbl | DOI

[8] X. Droubay, J. Justin and G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci. 255 (2001) 539–553. | MR | Zbl | DOI

[9] A. Glen, J. Justin, S. Widmer and L. Q. Zamboni, Palindromic richness. Eur. J. Combin. 30 (2009) 510–531. | MR | Zbl | DOI

[10] C. Guo, J. Shallit and A. M. Shur, Palindromic rich words and run-length encodings. Inform. Process. Lett. 116 (2016) 735–738. | MR | Zbl | DOI

[11] D. Kosolobov, M. Rubinchik and A. M. Shur, Pal^k is linear recognizable online, in SOFSEM 2015: Theory and Practice of Computer Science, edited by G. F. Italiano, T. Margaria-Steffen, J. Pokorný, J.-J. Quisquater and R. Wattenhofer. Springer, Berlin Heidelberg (2015) 289–301. | MR | Zbl

[12] E. Pelantová and Š. Starosta, On words with the zero palindromic defect, in Combinatorics on Words, edited by S. Brlek, F. Dolce, C. Reutenauer and É. Vandomme. Springer International Publishing, Cham (2017) 59–71. | MR | Zbl | DOI

[13] E. A. Petrova and A. M. Shur, Transition property for cube-free words, in Computer Science – Theory and Applications, edited by R. Van Bevern and G. Kucherov. Springer International Publishing, Cham (2019) 311–324. | MR | Zbl | DOI

[14] M. Rubinchik and A. M. Shur, The number of distinct subpalindromes in random words. Fund. Inform. 145 (2016) 371–384. | MR | Zbl

[15] J. Rukavicka, On the number of rich words, Developments in Language Theory: 21st International Conference, DLT 2017, Liège, Belgium, August 7–11, 2017. Proceedings, Springer International Publishing (2017) 345–352. | MR | Zbl

[16] J. Rukavicka, Transition property for α-power free languages with α ≥ 2 and k ≥ 3 letters, in Developments in Language Theory, edited by N. Jonoska and D. Savchuk. Springer International Publishing, Cham (2020) 294–303. | MR | Zbl | DOI

[17] L. Schaeffer and J. Shallit, Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences. Electr. J.Comb. 23 (2016) 1.25. | MR | Zbl | DOI

[18] J. Shallit and A. Shur, Subword complexity and power avoidance. Special issue in honor of the 70th birthday of Prof. Wojciech Rytter. Theor. Comp. Sci. 792 (2019) 96–116. | MR | Zbl

[19] J. Vesti, Extensions of rich words. Theor. Comput. Sci. 548 (2014) 14–24. | MR | Zbl | DOI