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

We relate the gapped k-deck problem introduced by Golm et al. (ISIT 2022) to notions arising in the literature of combinatorics on words. We consider the complexity functions of infinite sequences that count the number of factors up to the equivalence relation of strings having equal gapped k-decks. We show that the Thue–Morse sequence, the fixed point of the substitution 0↦01, 1↦10, has unbounded 1-gap k-binomial complexity for k ≥2. We also show that for a Sturmian sequence and g ≥1, all of its long enough factors are always pairwise g-gap k-binomially inequivalent for any k ≥2.

Generalizing the notion of the boundary sequence introduced by Chen and Wen, the $n$th term of the $\ell$-boundary sequence of an infinite word is the finite set of pairs $(u,v)$ of prefixes and suffixes of length $\ell$ appearing in factors $uyv$ of length $n+\ell$ ($n\ge \ell\ge 1$). Otherwise stated, for increasing values of $n$, one looks for all pairs of factors of length $\ell$ separated by $n-\ell$ symbols. For the large class of addable abstract numeration systems $S$, we show that if an infinite word is $S$-automatic, then the same holds for its $\ell$-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). To precise the limits of this result, we discuss examples of non-addable numeration systems and $S$-automatic words for which the boundary sequence is nevertheless $S$-automatic and conversely, $S$-automatic words with a boundary sequence that is not $S$-automatic. In the second part of the paper, we study the $\ell$-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word.

Given an integer base $b>1$, a set of integers is represented in base $b$ by a language over $\{0,1,...,b-1\}$. The set is said to be $b$-recognisable if its representation is a regular language. It is known that eventually periodic sets are $b$-recognisable in every base $b$, and Cobham's theorem implies the converse: no other set is $b$-recognisable in every base $b$. We are interested in deciding whether a $b$-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem decidable in 1986 and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first. In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case.

We characterize pairs of complementary nonhomogeneous Beatty sequences $(A_n)_{n>0}$ and $(B_n)_{n>0}$, with the restriction $A_1=1$ and $B_1\geq 3$, for which there exists an invariant take-away game having $\{(A_n,B_n),(B_n,A_n)\mid n> 0\}\cup\{(0,0)\}$ as a set of $P$-positions. Using the notion of a Sturmian word arising in combinatorics on words, this characterization can be translated into a decision procedure relying only on a few algebraic tests about algebraicity or rational independence. This work partially answers to a question of Larsson, Hegarty, and Fraenkel, raised in [Theoret. Comput. Sci., 412 (2011), pp. 729--735].

We compute the cardinality of the syntactic monoid of the language 0* repb (m$\mathbb{N}$) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integer