The structure of solutions to equations in free and virtually free groups

Abstract

I will describe work with Ciobanu and Diekert which expresses the full set of solutions to an equation or system of equations over a free group, and over a virtually free group, as an EDT0L language, and can be computed in PSPACE. EDT0L is a relatively simple formal language class, so it is surprising that what seemed like a complicated set has such an easy description. The new work with Diekert on virtually free groups reduces equations to systems of twisted equations using Bass-Serre theory.