Characterizations of families of morphisms and words via binomial complexities

Rigo, Michel; Stipulanti, Manon; Whiteland, Markus

doi:10.1016/j.ejc.2024.103932

Download

Article (Scientific journals)

Characterizations of families of morphisms and words via binomial complexities

Rigo, Michel; Stipulanti, Manon; Whiteland, Markus

2024 • In European Journal of Combinatorics

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/308062

DOI
10.1016/j.ejc.2024.103932

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

paper.pdf

Author preprint (542.85 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Factor complexity; Abelian complexity; Binomial complexity; powers of the Thue– Morse morphism; Sturmian words; Combinatorics on words

Abstract :

[en] Two words are k-binomially equivalent if each subword of length at most k occurs the same number of times in both words. The k-binomial complexity of an infinite word is a counting function that maps n to the number of k-binomial equivalence classes represented by its factors of length n. Cassaigne et al. [Int. J. Found. Comput. S., 22(4) (2011)] characterized a family of morphisms, which we call Parikh-collinear, as those morphisms that map all words to words with bounded 1-binomial complexity. Firstly, we extend this characterization: they map words with bounded k-binomial complexity to words with bounded (k + 1)-binomial complexity. As a consequence, fixed points of Parikh-collinear morphisms are shown to have bounded k- binomial complexity for all k. Secondly, we give a new characterization of Sturmian words with respect to their k-binomial complexity. Then we characterize recurrent words having, for some k, the same j-binomial complexity as the Thue–Morse word for all j ≤ k. Finally, inspired by questions raised by Lejeune, we study the relationships between the k- and (k + 1)-binomial complexities of infinite words; as well as the link with the usual factor complexity.

Disciplines :

Mathematics

Author, co-author :

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

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

Whiteland, Markus ; Université de Liège - ULiège > Mathematics

Language :

English

Title :

Characterizations of families of morphisms and words via binomial complexities

Publication date :

2024

Journal title :

European Journal of Combinatorics

ISSN :

0195-6698

eISSN :

1095-9971

Publisher :

Elsevier, Atlanta, Georgia

Peer reviewed :

Peer Reviewed verified by ORBi

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Available on ORBi :

since 23 October 2023

Statistics

Number of views

62 (7 by ULiège)

Number of downloads

27 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

Adamczewski, Boris, Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307:1 (2003), 47–75, 10.1016/S0304-3975(03)00092-6.
Adamczewski, Boris, Bugeaud, Yann, On the complexity of algebraic numbers. I. Expansions in integer bases. Ann. of Math. (2) 165:2 (2007), 547–565, 10.4007/annals.2007.165.547.
Allouche, Jean-Paul, Thue, combinatorics on words, and conjectures inspired by the Thue–Morse sequence. J. Théor. Nombres Bordeaux 27:2 (2015), 375–388 URL: http://jtnb.cedram.org/item?id=JTNB_2015__27_2_375_0.
Allouche, Jean-Paul, Shallit, Jeffrey, The ubiquitous Prouhet–Thue–Morse sequence. Ding, C., Helleseth, T., Niederreiter, H., (eds.) Sequences and their Applications, 1999, Springer London, London, 1–16, 10.1007/978-1-4471-0551-0_1.
Allouche, Jean-Paul, Shallit, Jeffrey, Automatic Sequences: Theory, Applications, Generalizations. 2003, Cambridge University Press, Cambridge, 10.1017/CBO9780511546563.
Atanasiu, Adrian, Martín-Vide, Carlos, Mateescu, Alexandru, On the injectivity of the Parikh matrix mapping. Fund. Inform. 49:4 (2002), 289–299.
Avgustinovich, Sergei V., Fon-Der-Flaass, Dmitriĭ G., Frid, Anna E., Arithmetical complexity of infinite words. Words, Languages & Combinatorics, III (Kyoto, 2000), 2003, World Sci. Publ., River Edge, NJ, 51–62, 10.1142/9789812704979_0004 2028864.
Berstel, Jean, Crochemore, Maxime, Pin, Jean-Éric, Thue-Morse sequence and p-adic topology for the free monoid. Discrete Math. 76:2 (1989), 89–94, 10.1016/0012-365X(89)90302-6.
Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and its Applications, 2010, Cambridge University Press, Cambridge, xx+615, 10.1017/CBO9780511777653.
Cassaigne, Julien, Fici, Gabriele, Sciortino, Marinella, Zamboni, Luca Q., Cyclic complexity of words. J. Combin. Theory Ser. A 145 (2017), 36–56, 10.1016/j.jcta.2016.07.002.
Cassaigne, Julien, Frid, Anna E., Puzynina, Svetlana, Zamboni, Luca Q., A characterization of words of linear complexity. Proc. Amer. Math. Soc. 147:7 (2019), 3103–3115, 10.1090/proc/14440.
Cassaigne, Julien, Karhumäki, Juhani, Puzynina, Svetlana, On k-abelian palindromes. Inform. and Comput. 260 (2018), 89–98, 10.1016/j.ic.2018.04.001.
Cassaigne, Julien, Karhumäki, Juhani, Saarela, Aleksi, On growth and fluctuation of k-abelian complexity. European J. Combin. 65 (2017), 92–105, 10.1016/j.ejc.2017.05.006.
Cassaigne, Julien, Richomme, Gwéenaël, Saari, Kalle, Zamboni, Luca Q., Avoiding abelian powers in binary words with bounded abelian complexity. Internat. J. Found. Comput. Sci. 22:4 (2011), 905–920, 10.1142/S0129054111008489.
Coven, Ethan M., Hedlund, G.A., Sequences with minimal block growth. Math. Syst. Theory 7:2 (1973), 138–153, 10.1007/BF01762232.
Droubay, Xavier, Pirillo, Giuseppe, Palindromes and Sturmian words. Theoret. Comput. Sci. 223:1–2 (1999), 73–85, 10.1016/S0304-3975(97)00188-6.
Erdős, Paul, Some unsolved problems. Michigan Math. J. 4 (1958), 291–300.
Fici, Gabriele, Puzynina, Svetlana, Abelian combinatorics on words: A survey. Comput. Sci. Rev., 47, 2023, 10.1016/j.cosrev.2022.100532 Paper No. 100532, 21.
Fleischmann, Pamela, Lejeune, Marie, Manea, Florin, Nowotka, Dirk, Rigo, Michel, Reconstructing words from right-bounded-block words. Internat. J. Found Comput. Sci. 32:6 (2021), 619–640, 10.1142/S0129054121420016.
Fossé, Stéphane, Richomme, Gwénaël, Some characterizations of Parikh matrix equivalent binary words. Inform. Process. Lett. 92:2 (2004), 77–82, 10.1016/j.ipl.2004.06.011.
Frid, Anna, Applying a uniform marked morphism to a word. Discrete Math. Theor. Comput. Sci. 3:3 (1999), 125–139, 10.46298/dmtcs.255.
Gawrychowski, Paweł, Kosche, Maria, Koß, Tore, Manea, Florin, Siemer, Stefan, Efficiently testing Simon's congruence. Bläser, Markus, Monmege, Benjamin, (eds.) 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 Leibniz International Proceedings in Informatics (LIPIcs), vol. 187, 2021, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 34:1–34:18, 10.4230/LIPIcs.STACS.2021.34.
Grillenberger, Christian, Constructions of strictly ergodic systems. I. Given entropy. Z. Wahrscheinlichkeit. 25 (1973), 323–334, 10.1007/BF00537161.
Kalašnik, L.I., The reconstruction of a word from fragments. Numerical Mathematics and Computer Technology, No. IV (Russian), 1973, Akad. Nauk Ukrain. SSR Fiz.-Tehn-Inst. Nizkih Temperatur, Kharkov, 56–57, 137.
Kamae, Teturo, Zamboni, Luca, Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Systems 22:4 (2002), 1191–1199, 10.1017/S0143385702000585.
Karhumäki, Juhani, Saarela, Aleksi, Zamboni, Luca Q., On a generalization of abelian equivalence and complexity of infinite words. J. Combin. Theory Ser. A 120:8 (2013), 2189–2206, 10.1016/j.jcta.2013.08.008.
Karhumäki, Juhani, Saarela, Aleksi, Zamboni, Luca Q., Variations of the Morse–Hedlund theorem for k-abelian equivalence. Acta Cybernet. 23:1 (2017), 175–189, 10.14232/actacyb.23.1.2017.11.
Lejeune, Marie, On the k-Binomial Equivalence of Finite Words and k-Binomial Complexity of Infinite Words. (Ph.D. thesis), 2021, Univ. of Liège URL: http://hdl.handle.net/2268/259266.
Lejeune, Marie, Leroy, Julien, Rigo, Michel, Computing the k-binomial complexity of the Thue–Morse word. J. Combin. Theory Ser. A, 176, 2020, 44, 10.1016/j.jcta.2020.105284.
Lejeune, Marie, Rigo, Michel, Rosenfeld, Matthieu, Templates for the k-binomial complexity of the tribonacci word. Adv. Appl. Math., 112, 2020, 26, 10.1016/j.aam.2019.101947.
Leroy, Julien, Rigo, Michel, Stipulanti, Manon, Generalized Pascal triangle for binomial coefficients of words. Adv. Appl. Math. 80 (2016), 24–47, 10.1016/j.aam.2016.04.006.
Lothaire, M., Combinatorics on Words. 1997, Cambridge Mathematical Library. Cambridge University Press, 10.1017/CBO9780511566097.
Lü, Xiao-Tao, Chen, Jin, Wen, Zhi-Xiong, Wu, Wen, On the 2-binomial complexity of the generalized Thue–Morse words. Theoret. Comput. Sci., 986, 2024, 114342, 10.1016/j.tcs.2023.114342.
Manvel, Bennet, Meyerowitz, Aaron D., Schwenk, Allen J., Smith, Kenneth W., Stockmeyer, Paul K., Reconstruction of sequences. Discrete Math. 94:3 (1991), 209–219, 10.1016/0012-365X(91)90026-X.
Mousavi, Hamoon, Automatic theorem proving in Walnut. 2016 arXiv, http://dx.doi.org/10.48550/ARXIV.1603.06017.
Ochsenschläger, Peter, Binomialkoeffizienten und Shuffle-Zahlen: Tech. Rep., 1981, Fachbereich Informatik, T.H. Darmstadt.
Peltomäki, Jarkko, Introducing privileged words: Privileged complexity of Sturmian words. Theoret. Comput. Sci. 500 (2013), 57–67, 10.1016/j.tcs.2013.05.028.
Pin, Jean-Éric, Silva, Pedro V., A noncommutative extension of Mahler's theorem on interpolation series. European J. Combin. 36 (2014), 564–578, 10.1016/j.ejc.2013.09.009.
Richomme, Gwénaël, Saari, Kalle, Zamboni, Luca Q., Balance and abelian complexity of the Tribonacci word. Adv. Appl. Math. 45:2 (2010), 212–231, 10.1016/j.aam.2010.01.006.
Richomme, Gwénaël, Saari, Kalle, Zamboni, Luca Q., Abelian complexity of minimal subshifts. J. Lond. Math. Soc. 83:1 (2011), 79–95, 10.1112/jlms/jdq063.
Richomme, Gwénaël, Séébold, Patrice, On factorially balanced sets of words. Theoret. Comput. Sci. 412:39 (2011), 5492–5497, 10.1016/j.tcs.2011.06.027.
Rigo, Michel, Relations on words. Indag. Math. (N.S.) 28:1 (2017), 183–204, 10.1016/j.indag.2016.11.018.
Rigo, Michel, Salimov, Pavel, Another generalization of abelian equivalence: Binomial complexity of infinite words. Theoret. Comput. Sci. 601 (2015), 47–57, 10.1016/j.tcs.2015.07.025.
Rigo, Michel, Stipulanti, Manon, Whiteland, Markus A., Binomial complexities and Parikh–collinear morphisms. Diekert, Volker, Volkov, Mikhail V., (eds.) Developments in Language Theory - 26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, Proceedings Lecture Notes in Computer Science, vol. 13257, 2022, Springer, 251–262, 10.1007/978-3-031-05578-2_20.
Rigo, Michel, Stipulanti, Manon, Whiteland, Markus A., Automaticity and Parikh-collinear morphisms. Combinatorics on Words Lecture Notes in Comput. Sci, vol. 13899, 2023, Springer, Cham, 247–260, 10.1007/978-3-031-33180-0_19.
Salomaa, Arto, Counting (scattered) subwords. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 81 (2003), 165–179.
Shallit, Jeffrey, The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut, London Mathematical Society Lecture Note Series, 2022, Cambridge University Press, 10.1017/9781108775267.
Whiteland, Markus A., Equations over the k-binomial monoids. Lecroq, Thierry, Puzynina, Svetlana, (eds.) Combinatorics on Words, 2021, Springer International Publishing, Cham, 185–197, 10.1007/978-3-030-85088-3_16.