JournalsggdVol. 7, No. 2pp. 323–355

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, Ukraine
  • Natalia V. Bondarenko

    Kyiv National University of Construction and Architecture, Ukraine
  • Said N. Sidki

    Universidade de Brasília, Brazil
  • Flavia R. Zapata

    Universidade de Brasília, Brasília, Brazil
On the conjugacy problem for finite-state automorphisms of regular rooted trees (with an appendix by Raphaël M. Jungers) cover
Download PDF

Abstract

We study the conjugacy problem in the automorphism group Aut(T)\operatorname{Aut}(T) of a regular rooted tree TT and in its subgroup FAut(T)\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 Aut(T)\operatorname{Aut}(T) if and only if they are conjugate in FAut(T)\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.

Cite this article

Ievgen Bondarenko, Natalia V. Bondarenko, Said N. Sidki, Flavia R. Zapata, 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), no. 2, pp. 323–355

DOI 10.4171/GGD/184