Multi-dimensional sets recognizable in all abstract numeration systems

DOI10.1051/ITA/2011112MaRDI QIDQ2911426zbMATH OpenOpenAlexFDO

Authors Émilie Charlier, Anne Lacroix, Narad Rampersad

Publication date 31 August 2012

Published in RAIRO. Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.5391, https://eudml.org/doc/222047

zbMATH Keywords

finite automata.multi-dimensional settingnumeration systemrecognizable sets of integersregular language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We prove that the subsets of N^d that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting.

Review text

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.

Recommendations

• Dimension of sets of numbers with multiple representations
• Multidimensional multiplicative large sets in totally minimal systems
• scientific article; zbMATH DE number 1817672
• Generalized number systems in Euclidean spaces
• Countable Dimensional Universal Sets
• A decision method for the recognizability of sets defined by number systems
• On recognizable sets of integers
• Recognizable sets of numbers in nonstandard bases
• Hyperarithmetical Sets
• Multidimensional covering systems of congruences

Cites work

• Abstract numeration systems
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3575557 (Why is no real title available?)
• scientific article; zbMATH DE number 1916667 (Why is no real title available?)
• Logic and p-recognizable sets of integers
• Multidimensional generalized automatic sequences and shape-symmetric morphic words
• Number representation and finite automata
• Numeration systems on a regular language
• On the base-dependence of sets of numbers recognizable by finite automata
• Radix enumeration of rational languages
• Semigroups, Presburger formulas, and languages
• Sets recognized by n-tape automata
• STACS 2004
• Synchronized rational relations of finite and infinite words

Cited in

(9)

• Affinely recursive sets and orderings of languages.
• Characterizing simpler recognizable sets of integers
• Decidability questions related to abstract numeration systems
• Regular sequences and synchronized sequences in abstract numeration systems
• Automatic winning shifts
• Abstract numeration systems on bounded languages and multiplication by a constant
• First-order logic and numeration systems
• On \(\frac{p}{q}\)-recognisable sets
• The growth function of S-recognizable sets

This page was built for publication: Multi-dimensional sets recognizable in all abstract numeration systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911426)