Multi-dimensional sets recognizable in all abstract numeration systems (Q2911426)

Let \(L\) be a regular language over an ordered alphabet. Enumerating the words of \(L\) by genealogical order gives rise to an abstract numeration system \(S\) in the sense of [\textit{P. B. A. Lecomte} and the reviewer, Theory Comput. Syst. 34, No. 1, 27--44 (2001; Zbl 0969.68095)]. A set \(X\) of integers is \(S\)-recognizable if the representations within \(S\) of the elements in \(X\) form a regular subset of \(L\). As usual, these notions are extended to subsets of \(\mathbb{N}^d\) with automata reading \(d\)-tuples of symbols.NEWLINENEWLINEIt is well known that a set \(X\subseteq\mathbb{N}\) is \(S\)-recognizable for all abstract numeration systems \(S\) if and only if \(X\) is ultimately periodic. The aim of this paper is to characterize the subsets of \(\mathbb{N}^d\) that are \(S\)-recognizable for all abstract systems \(S\). Using a classical decomposition result for regular languages [\textit{S. Eilenberg, C. C. Elgot} and \textit{J. C. Shepherdson}, J. Algebra 13, 447--464 (1969; Zbl 0207.02002)], it turns out that these sets are \(1\)-recognizable, i.e., recognizable for the abstract system built on \(a^{*}\), and thus form a proper subclass of the class of semi-linear sets.