[en] Parikh-collinear morphisms have recently received a lot of attention. They are defined by the property that the Parikh vectors of the images of letters are collinear. We first show that any fixed point of such a morphism is automatic. Consequently, we get under some mild technical assumption that the abelian complexity of a binary fixed
point of a Parikh-collinear morphism is also automatic, and we discuss a generalization to arbitrary alphabets.
Then, we consider the abelian complexity function of the fixed point of the Parikh-collinear morphism $0\mapsto 010011$, $1\mapsto 1001$. This $5$-automatic sequence is shown to be aperiodic, answering a question of Salo and Sportiello.
Disciplines :
Mathématiques
Auteur, co-auteur :
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
Allouche, J.-P., Shallit, J.: Automatic sequences are also non-uniformly morphic. In: Raigorodskii, A.M., Rassias, M.T. (eds.) Discrete Mathematics and Applications. SOIA, vol. 165, pp. 1–6. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-55857-4_1
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 1(2), 191–238 (1994). http://projecteuclid.org/euclid.bbms/1103408547, journées Montoises (Mons, 1992)
Büchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6, 66–92 (1960). https://doi.org/10.1002/malq.19600060105
Béal, M.P., Perrin, D., Restivo, A.: Recognizability of morphisms. Ergodic Theory Dyn. Syst. 1–25 (2023). https://doi.org/10.1017/etds.2022.109
Cassaigne, J., Nicolas, F.: Quelques propriétés des mots substitutifs. Bull. Belg. Math. Soc. Simon Stevin 10(suppl.), 661–676 (2003). http://projecteuclid.org/euclid.bbms/1074791324
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
Charlier, É., Leroy, J., Rigo, M.: Asymptotic properties of free monoid morphisms. Linear Algebra Appl. 500, 119–148 (2016). https://doi.org/10.1016/j.laa.2016.02. 030
Charlier, É., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comput. Sci. 23(5), 1035–1066 (2012). https://doi.org/10.1142/S0129054112400448
Cobham, A.: Uniform tag sequences. Math. Syst. Theory 6, 164–192 (1972). https://doi.org/10.1007/BF01706087
Dekking, F.M.: The spectrum of dynamical systems arising from substitutions of constant length. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 41(3), 221–239 (1978). https://doi.org/10.1007/BF00534241
Durand, F., Leroy, J.: The constant of recognizability is computable for primitive morphisms. Journal of Integer Sequences 20(#17.4.5) (2017). https://cs.uwaterloo. ca/journals/JIS/VOL20/Leroy/leroy4.html
Erdős, P.: Some unsolved problems. Michigan Math. J. 4, 291–300 (1958). https://doi.org/10.1307/mmj/1028997963
Fici, G., Puzynina, S.: Abelian combinatorics on words: a survey. Comput. Sci. Rev. 47, 100532 (2023). https://doi.org/10.1016/j.cosrev.2022.100532
Goč, D., Rampersad, N., Rigo, M., Salimov, P.: On the number of abelian bordered words (with an example of automatic theorem-proving). Internat. J. Found. Comput. Sci. 25(8), 1097–1110 (2014). https://doi.org/10.1142/S0129054114400267
Guo, Y.J., Lü, X.T., Wen, Z.X.: On the boundary sequence of an automatic sequence. Discrete Math. 345(1) (2022). https://doi.org/10.1016/j.disc. 2021.112632
Krawczyk, E., Müllner, C.: Automaticity of uniformly recurrent substitutive sequences (2023). https://doi.org/10.48550/arXiv.2111.13134
Mossé, B.: Reconnaissabilité des substitutions et complexité des suites automa-tiques. Bulletin de la Société Mathématique de France 124(2), 329–346 (1996). https://doi.org/10.24033/bsmf.2283
Mossé, B.: Puissance de mots et reconnaissabilité des points fixes d’une substitution. Theor. Comput. Sci. 99(2), 327–334 (1992). https://doi.org/10.1016/0304-3975(92)90357-L
Mousavi, H.: Automatic theorem proving in Walnut (2016). https://doi.org/10. 48550/ARXIV.1603.06017
Parreau, A., Rigo, M., Rowland, E., Vandomme, É.: A new approach to the 2-regularity of the ℓ-abelian complexity of 2-automatic sequences. Electron. J. Comb. 22(#P1.27) (2022). https://doi.org/10.37236/4478
Puzynina, S., Whiteland, M.A.: Abelian closures of infinite binary words. J. Comb. Theory Ser. A 185, 105524 (2022). https://doi.org/10.1016/j.jcta.2021.105524
Rigo, M.: Formal languages, automata and numeration systems. Vol. 1. ISTE, London; John Wiley & Sons Inc, Hoboken, NJ (2014), introduction to combinatorics on words, With a foreword by Valérie Bethé. https://doi.org/10.1002/9781119008200
Rigo, M.: Formal languages, automata and numeration systems. Vol. 2. Networks and Telecommunications Series, ISTE, London; John Wiley & Sons Inc, Hoboken, NJ (2014), applications to recognizability and decidability, With a foreword by Valérie Berthé. https://doi.org/10.1002/9781119042853
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. In: Diekert, V., Volkov, M.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, pp. 251– 262. Springer (2022). https://doi.org/10.1007/978-3-031-05578-2_20
Schaeffer, L.: Deciding Properties of Automatic Sequences. Master’s thesis, Univ. of Waterloo (2013). https://uwspace.uwaterloo.ca/handle/10012/7899
Shallit, J.: Abelian complexity and synchronization. INTEGERS: Electron. J. Comb. Number Theory (#A.36) (2021). http://math.colgate.edu/integers/v36/v36.pdf
Shallit, J.: The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut. London Mathematical Society Lecture Note Series, Cambridge University Press (2022). https://doi.org/10.1017/9781108775267
