String attractors of fixed points of k-bonacci-like morphisms

[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.

Disciplines :

Mathematics

Author, co-author :

Gheeraert, France ; Université de Liège - ULiège > Mathematics

Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Giuseppe Romana; UniPa - Università degli Studi di Palermo [IT] > Dipartimento di Matematica e Informatica

Language :

English

Title :

String attractors of fixed points of k-bonacci-like morphisms

Publication date :

31 May 2023

Event name :

WORDS 2023

Event place :

Umeå, Sweden

Event date :

12-16 juin 2023

Audience :

International

Main work title :

Combinatorics on Words. WORDS 2023

Editor :

Frid, Anna

Mercaş, Robert

Publisher :

Springer, Cham, Switzerland

ISBN/EAN :

978-3-031-33179-4

Collection name :

Lecture Notes in Computer Science

Collection ISSN :

0302-9743

Peer reviewed :

Peer reviewed

Funding number :

F.R.S.-FNRS - Fonds de la Recherche Scientifique; MIUR project PRIN 2017 ADASCOML – 2017K7XPAN

Available on ORBi :

since 27 February 2023

Statistics

Number of views

85 (20 by ULiège)

Number of downloads

64 (5 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

Allouche, J.P., Shallit, J.: Automatic sequences, theory, applications, generalizations Cambridge University Press, Cambridge (2003). https://doi.org/10.1017/CBO9780511546563
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
Christiansen, A.R., Ettienne, M.B., Kociumaka, T., Navarro, G., Prezza, N.: Optimal-time dictionary-compressed indexes. ACM Trans. Algorithms 17(1), 8:1– 8:39 (2021). https://doi.org/10.1145/3426473
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