Independent numeration systems and syndeticity
type: Item
instance of: scholarly article
title: Independent numeration systems and syndeticity
zbMATH Open document ID: 0952.68073
DOI: 10.1016/S0304-3975(98)00035-8
author: Georges Hansel
published in: Theoretical Computer Science
publication date: 1999-01-12T00:00:00Z
review text: The famous Cobham's theorem [\textit{A.~Cobham}, Math.~System Theory 3, 186--192 (1969; Zbl 0179.02501)] asserts that a set \(X\) of natural numbers is recognizable in two multiplicatively independent bases if and only if \(X\) is ultimately periodic. In the original paper the bases are natural numbers. Similar statements have been proved for numeration systems as defined by \textit{A. Bertrand-Mathis} [Acta Math. Hung. 54, No. 3--4, 237--241 (1989; Zbl 0695.10005)] and for subsets of \(\mathbb N ^k\). All these generalizations needed the hypothesis the base of the numeration system is a Pisot number. The main result of the paper under review asserts the syndeticity of any infinite set of natural numbers which is \(\theta\)-recognizable and \(\theta '\)-recognizable for some multiplicatively independent real numbers \(\theta, \theta ' >1\). As an application one derives a result of Cobham's theorem type for subsets of \(\mathbb N ^k\). This result has been obtained independently by a different method by \textit{A.~Bès} [J.~Symb. Logic 65, No. 1, 201--211 (2000; Zbl 0958.03025)]. (Reviewer's remark: the reference [6] in the paper under review should be \textit{A.~Cobham} [Math.~System Theory 3, 186--192 (1969)]).
reviewed by: Mihai Cipu
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 11A63
zbMATH DE Number: 1238867
zbMATH Keywords: numeration systems
zbMATH Keywords: finite automaton
zbMATH Keywords: Cobham's theorem
MaRDI profile type: Publication
cites work: How to write integers in a non-integral basis
cites work: An extension of the Cobham-Semënov Theorem
cites work: Bertrand numeration systems and recognizability
cites work: Logic and \(p\)-recognizable sets of integers
cites work: On the base-dependence of sets of numbers recognizable by finite automata
cites work: Q4079524
cites work: Q4880554
cites work: Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
full work available at URL: s0304-3975(98)00035-8
OpenAlex ID: W2482394447
description: scientific article; zbMATH DE number 1238867