- journal article metadata
European Mathematical Society Publishing House
2016-09-19 17:04:59
Groups, Geometry, and Dynamics
Groups Geom. Dyn.
GGD
1661-7207
1661-7215
Group theory and generalizations
10.4171/GGD
http://www.ems-ph.org/doi/10.4171/GGD
subscribers, moving wall 5 years
European Mathematical Society Publishing House
Zuerich, Switzerland
© European Mathematical Society
7
2013
2
On the conjugacy problem for finite-state automorphisms of regular rooted trees (with an appendix by Raphaël M. Jungers)
Ievgen
Bondarenko
Taras Shevchenko National University of Kyiv, KYIV, UKRAINE
Natalia
Bondarenko
Kyiv National University of Construction and Architecture, KYIV, UKRAINE
Said
Sidki
Universidade de Brasília, BRASÍLIA-DF, BRAZIL
Flavia
Zapata
Universidade de Brasília, BRASÍLIA-DF, BRAZIL
Automorphism of a rooted tree, conjugacy problem, finite-state automorphism, finite automaton, bounded automaton
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.
Group theory and generalizations
General
323
355
10.4171/GGD/184
http://www.ems-ph.org/doi/10.4171/GGD/184