Groups, Geometry, and Dynamics


Full-Text PDF (329 KB) | Metadata | Table of Contents | GGD summary
Volume 7, Issue 2, 2013, pp. 323–355
DOI: 10.4171/GGD/184

Published online: 2013-05-07

On the conjugacy problem for finite-state automorphisms of regular rooted trees (with an appendix by Raphaël M. Jungers)

Ievgen Bondarenko[1], Natalia V. Bondarenko[2], Said N. Sidki[3] and Flavia R. Zapata[4]

(1) Taras Shevchenko National University of Kyiv, Ukraine
(2) Kyiv National University of Construction and Architecture, Ukraine
(3) Universidade de Brasília, Brazil
(4) Universidade de Brasília, Brasília, Brazil

We study the conjugacy problem in the automorphism group $\operatorname{Aut}(T)$ of a regular rooted tree $T$ and in its subgroup $\operatorname{FAut}(T)$ of finite-state automorphisms. We show that under the contracting condition and the finiteness of what we call the orbit-signalizer, two finite-state automorphisms are conjugate in $\operatorname{Aut}(T)$ if and only if they are conjugate in $\operatorname{FAut}(T)$, and that this problem is decidable. We prove that both conditions are satisfied by bounded automorphisms and establish that the (simultaneous) conjugacy problem in the group of bounded automata is decidable.

Keywords: Automorphism of a rooted tree, conjugacy problem, finite-state automorphism, finite automaton, bounded automaton

Bondarenko Ievgen, Bondarenko Natalia, Sidki Said, Zapata Flavia: On the conjugacy problem for finite-state automorphisms of regular rooted trees (with an appendix by Raphaël M. Jungers). Groups Geom. Dyn. 7 (2013), 323-355. doi: 10.4171/GGD/184