Groups with Context-Free Conjugacy Problems
Derek F. Holt, Sarah Rees, Claas E. R\"over
Keywords conjugacy problem, context-free languages, indexed languages
Status published in Int J Alg Comp
\noindent 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
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 $\delta$-hyperbolic group
and any $\lambda \ge 1$, $\epsilon \ge 0$,
the intersection of the inverse conjugacy problem with the set of pairs of
$(\lambda,\epsilon)$-quasigeodesics is context-free.
Finally we show that the conjugacy problem of a virtually free group is
an asynchronously indexed language.
The preprint is available as gzipped
dvi (68 kB),
postscript (184 kB) and
Alternatively, you can request a copy by