Geodesic languages for rational subsets and conjugates in virtually free groups

Abstract

We prove that a subset of a virtually free group is rational if and only if the language of geodesic words representing its elements (in any generating set) is rational and that the language of geodesics representing conjugates of elements in a rational subset of a virtually free group is context-free. As a corollary, the doubly generalized conjugacy problem is decidable for rational subsets of finitely generated virtually free groups: there is an algorithm taking as input two rational subsets K1 and K2 of a virtually free group that decides whether there is one element of K1 conjugate to an element of K2. For free groups, we prove that the same problem is decidable with rational constraints on the set of conjugators. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons.org/licenses/by/4.0/).