Abstract
The palindromic length \(\mathrm {PL}(v)\) of a finite word v is the minimal number of palindromes whose concatenation is equal to v. In 2013, Frid, Puzynina, and Zamboni conjectured that: If w is an infinite word and k is an integer such that \(\mathrm {PL}(u)\le k\) for every factor u of w then w is ultimately periodic.
Suppose that w is an infinite word and k is an integer such \(\mathrm {PL}(u)\le k\) for every factor u of w. Let \({\varOmega (w,k)}\) be the set of all factors u of w that have more than \(\root k \of {k^{-1}\vert u\vert }\) palindromic prefixes. We show that \({\varOmega (w,k)}\) is an infinite set and we show that for each positive integer j there are palindromes a, b and a word such that \((ab)^j\) is a factor of u and b is nonempty. Note that \((ab)^j\) is a periodic word and \((ab)^ia\) is a palindrome for each \(i\le j\). These results justify the following question: What is the palindromic length of a concatenation of a suffix of b and a periodic word \((ab)^j\) with “many” periodic palindromes?
It is known that if u, v are nonempty words then \(|\mathrm {PL}(uv)-\mathrm {PL}(u)|\le \mathrm {PL}(v)\). The main result of our article shows that if a, b are palindromes, b is nonempty, u is a nonempty suffix of b, \(\vert ab\vert \) is the minimal period of aba, and j is a positive integer with \(j\ge 3\mathrm {PL}(u)\) then \(\mathrm {PL}(u(ab)^j)-\mathrm {PL}(u)\ge 0\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ambrož, P., Kadlec, O., Masáková, Z., Pelantová, E.: Palindromic length of words and morphisms in class P. Theor. Comput. Sci. 780, 74–83 (2019). https://doi.org/10.1016/j.tcs.2019.02.024
Ambrož, P., Pelantová, E.: On palindromic length of Sturmian sequences. In: Hofman, P., Skrzypczak, M. (eds.) Developments in Language Theory, pp. 244–250. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-030-24886-4_18
Borozdin, K., Kosolobov, D., Rubinchik, M., Shur, A.M.: Palindromic length in linear time. In: Kärkkäinen, J., Radoszewski, J., Rytter, W. (eds.) 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 78, pp. 23:1–23:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017). https://doi.org/10.4230/LIPIcs.CPM.2017.23
Bucci, M., Richomme, G.: Greedy palindromic lengths. Int. J. Found. Comput. Sci. 29(03), 331–356 (2018). https://doi.org/10.1142/S0129054118500077
Fici, G., Gagie, T., Kräkkäinen, J., Kempa, D.: A subquadratic algorithm for minimum palindromic factorization. J. Discrete Algorithms 28, 41–48 (2014). https://doi.org/10.1016/j.jda.2014.08.001. stringMasters 2012 & 2013 Special Issue (Volume 1)
Frid, A., Puzynina, S., Zamboni, L.: On palindromic factorization of words. Adv. Appl. Math. 50(5), 737–748 (2013). https://doi.org/10.1016/j.aam.2013.01.002
Frid, A.E.: Sturmian numeration systems and decompositions to palindromes. Eur. J. Comb. 71, 202–212 (2018). https://doi.org/10.1016/j.ejc.2018.04.003
Frid, A.E.: First lower bounds for palindromic length. In: Hofman, P., Skrzypczak, M. (eds.) Developments in Language Theory, pp. 234–243. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-030-24886-4_17
Kosolobov, D., Rubinchik, M., Shur, A.M.: Pal\(^k\) is linear recognizable online. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.J., Wattenhofer, R. (eds.) SOFSEM 2015: Theory and Practice of Computer Science, pp. 289–301. Springer, Berlin Heidelberg, Berlin, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46078-8_24
Rubinchik, M., Shur, A.M.: EERTREE: an efficient data structure for processing palindromes in strings. In: Lipták, Z., Smyth, W.F. (eds.) IWOCA 2015. LNCS, vol. 9538, pp. 321–333. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29516-9_27
Saarela, A.: Palindromic length in free monoids and free groups. In: Brlek, S., Dolce, F., Reutenauer, C., Vandomme, É. (eds.) WORDS 2017. LNCS, vol. 10432, pp. 203–213. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66396-8_19
Acknowledgments
This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS20/183/OHK4/3T/14.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Rukavicka, J. (2020). Palindromic Length of Words with Many Periodic Palindromes. In: Jirásková, G., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science(), vol 12442. Springer, Cham. https://doi.org/10.1007/978-3-030-62536-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-62536-8_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62535-1
Online ISBN: 978-3-030-62536-8
eBook Packages: Computer ScienceComputer Science (R0)