zbMATH — the first resource for mathematics

Combinatorial and dynamical study of substitutions around the theorem of Cobham. (English) Zbl 1038.11016
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].

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