×

Rational tree morphisms and transducer integer sequences: definition and examples. (English) Zbl 1165.11086

In this interesting paper the author defines transducer integer sequences: these are sequences of integers generated by transducers, i.e., essentially by finite automata where the output depends on the final state attained and on each transition step taken during the computation. These sequences are related to, but different from automatic sequences. These transducers generate self-similar (semi-)groups of trees auto- or endomorphisms, relating them to the theory of self-similar groups, see [V. Nekrashevych, Self-similar groups. Mathematical Surveys and Monographs 117. Providence, RI: American Mathematical Society (AMS) (2005; Zbl 1087.20032)] also known as automata groups, see [R. I. Grigorchuk,V. V. Nekrashevich and V. I. Sushchanskii, Automata, dynamical systems, and groups. Proc. Steklov Inst. Math. 231, 128–203 (2000); translation from Tr. Mat. Inst. Steklova 231, 134–214 (2000; Zbl 1155.37311)] or state-closed groups, see [M. V. Volkov, Izv. Ural. Gos. Univ. 22, Mat. Mekh. 4, 43–61 (2002; Zbl 1069.20054)], which is a field both very active and connected to numerous other fields, as shown by the bibliography of the paper under review.

MSC:

11Y55 Calculation of integer sequences
11B85 Automata sequences
20M20 Semigroups of transformations, relations, partitions, etc.
20M35 Semigroups in automata theory, linguistics, etc.

Software:

OEIS
PDFBibTeX XMLCite
Full Text: arXiv EuDML EMIS