Generalized conjugacy from a language-theoretical perspective

The conjugacy problem is, alongside the word and the isomorphism problems, one of the three classical algorithmic problems in group theory introduced by Max Dehn in 1911. It asks whether it is decidable if two given elements of a group are conjugate. Since its introduction, the problem has been extensively studied from algebraic, asymptotic, topological, and language-theoretical perspectives. The generalized conjugacy problem, which asks whether a given element has a conjugate lying in a subset of the group, has followed a similar trajectory and likewise admits rich developments in these areas.

In this talk, we explore the language-theoretical aspects of the generalized conjugacy problem. Specifically, we introduce the notion of relative conjugacy languages, extending the conjugacy languages defined by Ciobanu, Hermiller, Holt, and Rees, and study its nature for several classes of groups, such as free, hyperbolic, or virtually abelian. We also examine relative conjugacy growth and show that, relative to rational subsets of the free group, it is either polynomial of any degree or exponential, but never intermediate.

This is joint work with Ana-Catarina Monteiro.