Binomial Complexities and Parikh-Collinear Morphisms

[en] Two words are k-binomially equivalent, if each word of length at most k occurs as a subword, or scattered factor, the same number of times in both words. The k-binomial complexity of an infinite word maps the natural n to the number of k-binomial equivalence classes represented by its factors of length n. Inspired by questions raised by Lejeune, we study the relationships between the k and (k+1)-binomial complexities; as well as the link with the usual factor complexity. We show that pure morphic words obtained by iterating a Parikh-collinear morphism, i.e. a morphism mapping all words to words with bounded abelian complexity, have bounded k-binomial complexity. In particular, we study the properties of the image of a Sturmian word by an iterate of the Thue-Morse morphism.

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 > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Binomial Complexities and Parikh-Collinear Morphisms

Publication date :

2022

Event name :

Developments in Language Theory

Event date :

du 9 mai 2022 au 13 mai 2022

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Heidelberg, Germany

Volume :

13257

Pages :

251-262

Peer reviewed :

Peer reviewed

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]

Available on ORBi :

since 13 January 2022

Statistics

Number of views

71 (12 by ULiège)

Number of downloads

52 (4 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Allouche, J.P., Shallit, J.: Automatic Sequences Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003). https://doi.org/10.1017/CBO9780511546563
Cassaigne, J., Fici, G., Sciortino, M., Zamboni, L.Q.: Cyclic complexity of words. J. Comb. Theory Ser. A 145, 36–56 (2017). https://doi.org/10.1016/j.jcta.2016. 07.002
Cassaigne, J., Richomme, G., Saari, K., Zamboni, L.Q.: Avoiding Abelian powers in binary words with bounded Abelian complexity. Int. J. Found. Comput. S. 22(4), 905–920 (2011). https://doi.org/10.1142/S0129054111008489
Cheraghchi, M., Gabrys, R., Milenkovic, O., Ribeiro, J.: Coded trace reconstruction. IEEE Trans. Inf. Theory 66(10), 6084–6103 (2020). https://doi.org/10.1109/TIT.2020.2996377
Dudík, M., Schulman, L.J.: Reconstruction from subsequences. J. Comb. Theory, Ser. A 103(2), 337–348 (2003). https://doi.org/10.1016/S0097-3165(03)00103-1
Frid, A.: Applying a uniform marked morphism to a word. Discrete Math Theor. Comput. Sci. 3(3), 125–139 (1999). https://doi.org/10.46298/dmtcs.255
Grillenberger, C.: Constructions of strictly ergodic systems. I. Given entropy. Z. Wahrscheinlichkeit. 25, 323–334 (1973). https://doi.org/10.1007/BF00537161
Karhumäki, J., Saarela, A., Zamboni, L.Q.: On a generalization of Abelian equivalence and complexity of infinite words. J. Comb. Theory Ser. A 120(8), 2189–2206 (2013). https://doi.org/10.1016/j.jcta.2013.08.008
Lejeune, M.: On the k-binomial equivalence of finite words and k-binomial complexity of infinite words. Ph.D. thesis, University of Liège (2021). http://hdl.handle. net/2268/259266
Lejeune, M., Leroy, J., Rigo, M.: Computing the k-binomial complexity of the Thue-Morse word. J. Comb. Theory Ser. A 176, 44 (2020). https://doi.org/10. 1016/j.jcta.2020.105284
Lejeune, M., Rigo, M., Rosenfeld, M.: Templates for the k-binomial complexity of the Tribonacci word. Adv. Appl. Math. 112, 26 (2020). https://doi.org/10.1016/j.aam.2019.101947
Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997). https://doi.org/10.1017/CBO9780511566097
Lü, X.T., Chen, J., Wen, Z.X., Wu, W.: On the 2-binomial complexity of the generalized Thue-Morse words (2021, preprint). https://arxiv.org/abs/2112.05347
Ochsenschläger, P.: Binomialkoeffizienten und shuffle-zahlen. T.H. Darmstadt, Technischer bericht, Fachbereicht Informatik (1981)
Peltomäki, J.: Introducing privileged words: Privileged complexity of Sturmian words. Theor. Comput. Sci. 500, 57–67 (2013). https://doi.org/10.1016/j.tcs.2013. 05.028
Rigo, M.: Relations on words. Indag Math. New Ser. 28(1), 183–204 (2017). https://doi.org/10.1016/j.indag.2016.11.018
Rigo, M., Salimov, P.: Another generalization of abelian equivalence: binomial complexity of infinite words. Theor. Comput. Sci. 601, 47–57 (2015). https://doi. org/10.1016/j.tcs.2015.07.025
Rigo, M., Stipulanti, M., Whiteland, M.A.: Binomial complexities and Parikh-collinear morphisms (2022, preprint). https://arxiv.org/abs/2201.04603
Whiteland, M.A.: Equations over the k-binomial monoids. In: Lecroq, T., Puzynina, S. (eds.) WORDS 2021. LNCS, vol. 12847, pp. 185–197. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-85088-3 16