Automatic Abelian Complexities of Parikh-Collinear Fixed Points

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

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 erasing, 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.

;Comment: 18 pages, 2 figures, 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]