Groups with context-free conjugacy problems
Derek Holt, Sarah Rees, Claas Röver
Abstract
The conjugacy problem and the inverse conjugacy problem of a finitely
generated group are defined, from a language theoretic point of view,
as sets of pairs of words. An automaton might be obliged to read the two
input words synchronously, or could have the option to read asynchronously.
Hence each class of languages gives rise to four classes of groups; groups
whose (inverse) conjugacy problem is an (a)synchronous language in the given
class. For regular languages all these classes are identical with the class of
finite groups. We show that the finitely generated groups with asynchronously
context-free inverse conjugacy problem are precisely the virtually free groups.
Moreover, the other three classes arising from context-free languages are
shown all to coincide with the class of virtually cyclic groups, which is
precisely the class of groups with synchronously one-counter (inverse)
conjugacy problem. It is also proved that, for a δ-hyperbolic group and
any λ > 1, ε > 0, the intersection of the inverse
conjugacy problem with the set of pairs of (λ,ε)-quasigeodesics
is context-free. Finally we show that the conjugacy problem of a virtually
free group is an asynchronously indexed language.
This is published in in Internat. J. Algebra Comput. 21 (2011), no. 1-2, 193-216
Of course you can also ask me for a hard copy.