×

A generalization of Cobham’s theorem. (Une généralisation du théorème de Cobham.) (French) Zbl 0814.11015

The author generalizes the notion of \(q\)-automaticity by defining \(\theta\)-automaticity where \(\theta\) is a Pisot number. He then shows a Cobham-like theorem: the Cobham theorem [A. Cobham, Math. Syst. Theory 3, 186-192 (1969; Zbl 0179.025)] asserts that if a sequence is both \(k\)- and \(l\)-automatic, where \(\log k/\log l \in \mathbb{R}\setminus \mathbb{Q}\), then this sequence is ultimately periodic.
In the paper under review the author shows that if a sequence is both \(q\)-automatic and \(\theta\)-automatic (where \(q\) is an integer \(> 1\) and \(\theta\) a unitary Pisot number satisfying an extra assumption), then the sequence is ultimately periodic. He also indicates that the proof can be extended by replacing “\(\theta\) unitary Pisot” by “\(\theta\) Pisot and the constant term \(\alpha\) of its minimal polynomial prime to \(q\)”. To have a generalization of Cobham’s theorem one would like to replace “\(\alpha\) prime to \(q\)” by “\(\alpha\) such that \(\log \alpha/\log q \in \mathbb{R}\setminus \mathbb{Q}\)”.

MSC:

11B85 Automata sequences
68R15 Combinatorics on words
68Q45 Formal languages and automata

Citations:

Zbl 0179.025
PDF BibTeX XML Cite
Full Text: DOI EuDML