[en] Parikh-collinear morphisms have the property that all the Parikh vectors of the images of letters are collinear, i.e., the associated adjacency matrix has rank 1. In the conference DLT-WORDS 2023 we showed that fixed points of Parikh-collinear morphisms are automatic. We also showed that the abelian complexity function of a binary fixed point of such a morphism is automatic under some assump- tions. In this note, we fully generalize the latter result. Namely, we show that the abelian complexity function of a fixed point of an arbitrary, possibly eras- ing, Parikh-collinear morphism is automatic. Furthermore, a deterministic finite automaton with output generating this abelian complexity function is provided by an effective procedure. To that end, we discuss the constant of recognizability of a morphism and the related cutting set.
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
Automatic Abelian Complexities of Parikh-Collinear Fixed Points
Publication date :
2024
Number of pages :
18
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique
Commentary :
Long version of [M. Rigo, M. Stipulanti, M. A. Whiteland, Automaticity and Parikh-collinear morphisms. In: Combinatorics on Words. Lecture Notes in Comput. Sci., vol. 13899, pp. 247–260. Springer, 2023. https://doi.org/10.1007/ 978-3-031-33180-0 19]