Combinatorial and dynamical study of substitutions around the theorem of Cobham. (English) Zbl 1038.11016

Durand, Fabien

Maass, Alejandro (ed.) et al., Dynamics and randomness. Lectures given at the conference, Universidad de Chile, Santiago, Chile, December 11–15, 2000. Dordrecht: Kluwer Academic Publishers (ISBN 1-4020-0591-1/hbk). Nonlinear Phenom. Complex Syst. 7, 53-94 (2002).

A theorem due to Cobham going back to 1969 asserts that a non-ultimately periodic sequence on a finite alphabet cannot be simultaneously \(p\)-automatic and \(q\)-automatic if \(p\) and \(q\) are multiplicatively independent integers. This paper is an account of the state of the art for generalizations of this result (several of them are due to the author of the paper under review). Please note that reference [C. Holton, L. Q. Zamboni, Theory Comput. Syst. 34, 545–564 (2001; Zbl 0993.68075)] has appeared.
For the entire collection see [Zbl 1019.00010].

Reviewer: Jean-Paul Allouche (Orsay)

MSC:

11B85	Automata sequences
37B10	Symbolic dynamics
03D05	Automata and formal grammars in connection with logical questions
68Q45	Formal languages and automata
68R15	Combinatorics on words

Citations:

Zbl 0993.68075