[en] Firstly studied by Kempa and Prezza in 2018 as the cement of text compression algorithms, string attractors have become a compelling object of theoretical research within the community of combinatorics on words. In this context, they have been studied for several families of finite and infinite words. In this paper, we obtain string attractors of prefixes of particular infinite words generalizing k-bonacci words (including the famous Fibonacci word) and obtained as fixed points of k-bonacci-like morphisms. In fact, our description involves the numeration systems classically derived from the considered morphisms.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Berthé, V., Rigo, M. (eds.): Combinatorics, automata and number theory, Encyclopedia of Mathematics and its Applications, vol. 135. Cambridge University Press, Cambridge (2010). https://doi.org/10.1017/CBO9780511777653
Bertrand-Mathis, A.: Comment écrire les nombres entiers dans une base qui n’est pas entière. Acta Math. Hungar. 54(3–4), 237–241 (1989). https://doi.org/10. 1007/BF01952053
Bonizzoni, P., De Felice, C., Zaccagnino, R., Zizza, R.: Inverse Lyndon words and inverse Lyndon factorizations of words. Adv. in Appl. Math. 101, 281–319 (2018). https://doi.org/10.1016/j.aam.2018.08.005
Charlier, E., Cisternino, C., Stipulanti, M.: A full characterization of Bertrand numeration systems. In: Developments in Language Theory, vol. 13257. LNCS, pp. 102–114. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-05578-2_8
Charlier, E., Philibert, M., Stipulanti, M.: Nyldon words. J. Combin. Theory Ser. A 167, 60–90 (2019). https://doi.org/10.1016/j.jcta.2019.04.002
Chen, K.T., Fox, R.H., Lyndon, R.C.: Free differential calculus. IV. The quotient groups of the lower central series. Ann. of Math. 2(68), 81–95 (1958). https://doi. org/10.2307/1970044
Dumont, J.M., Thomas, A.: Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci. 65(2), 153–169 (1989). https://doi.org/10.1016/0304-3975(89)90041-8
Duval, J.P.: Mots de Lyndon et périodicité. RAIRO Inform. Théor. 14(2), 181–191 (1980). https://doi.org/10.1051/ita/1980140201811
Dvořáková, L.: String attractors of episturmian sequence, preprint available at arXiv:2211.01660 (2022)
Fabre, S.: Substitutions et β-systèmes de numération. Theoret. Comput. Sci. 137(2), 219–236 (1995). https://doi.org/10.1016/0304-3975(95)91132-A
Frougny, C.: On the sequentiality of the successor function. Inform. Comput. 139(1), 17–38 (1997). https://doi.org/10.1006/inco.1997.2650
Gewurz, D.A., Merola, F.: Numeration and enumeration. European J. Combin. 33(7), 1547–1556 (2012). https://doi.org/10.1016/j.ejc.2012.03.017
Gheeraert, F., Restivo, A., Romana, G., Sciortino, M., Stipulanti, M.: New string attractor-based complexities on infinite words (2023), work in progress
Gheeraert, F., Romana, G., Stipulanti, M.: String attractors of fixed points of k-bonacci-like morphisms, long version available at arXiv:2302.13647 (2023)
Hollander, M.: Greedy numeration systems and regularity. Theory Comput. Syst. 31(2), 111–133 (1998). https://doi.org/10.1007/s002240000082
Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: STOC 2018–Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 827–840. ACM, New York (2018). https://doi.org/10. 1145/3188745.3188814
Kutsukake, K., Matsumoto, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: On repetitiveness measures of Thue-Morse words. In: Boucher, C., Thankachan, S.V. (eds.) SPIRE 2020. vol. 12303. LNCS, pp. 213–220. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59212-7_15
Lecomte, P.B.A., Rigo, M.: Numeration systems on a regular language. Theory Comput. Syst. 34(1), 27–44 (2001). https://doi.org/10.1007/s002240010014
Lothaire, M.: Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997). https://doi.org/10.1017/CBO9780511566097, corrected reprint of the 1983 original
Mantaci, S., Restivo, A., Romana, G., Rosone, G., Sciortino, M.: A combinatorial view on string attractors. Theoret. Comput. Sci. 850, 236–248 (2021). https://doi. org/10.1016/j.tcs.2020.11.006
Parry, W.: On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar. 11, 401–416 (1960). https://doi.org/10.1007/BF02020954
Restivo, A., Romana, G., Sciortino, M.: String attractors and infinite words. In: LATIN 2022: Theoretical informatics, vol. 13568. LNCS, pp. 426–442. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-20624-5_26
Reutenauer, C.: Mots de Lyndon généralisés. Sém. Lothar. Combin. 54, Art. B54h, 16 (2005/07)
Rigo, M.: Formal languages, automata and numeration systems. 2. Applications to recognizability and decidability. Networks and Telecommunications Series, ISTE, London; John Wiley & Sons Inc, Hoboken, NJ (2014). https://doi.org/10.1002/9781119042853
Schaeffer, L., Shallit, J.: String attractor for automatic sequences, preprint available at arXiv:2012.06840 (2022)
Shallit, J.: The logical approach to automatic sequences. Exploring combinatorics on words with Walnut, Lond. Math. Soc, vol. 482. Lecture Notes Series. Cambridge University Press, Cambridge (2023). https://doi.org/10.1017/9781108775267
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
