Armin Weiss(Stuttgart)), `On the isomorphism problem for virtually free groups'

Abstract: The isomorphism problem for virtually free groups has been shown to be decidable by Krstic. Later the complexity has been improved to primitive recursive by Senizergues in the case that the input is either given as two context free grammars for the word problems or as finite extensions of free groups. We present an algorithm for the following problem: given a context-free grammar for the word problem of a virtually free group G, compute a finite graph of groups with finite vertex groups and fundamental group G. Our algorithm is non-deterministic and runs in doubly exponential time. Using Krstic's algorithm for testing fundamental groups of graphs of groups for isomorphism, it follows that the isomorphism problem of context-free groups can be solved in doubly exponential space. Moreover, if, instead of a grammar, a finite extension of a free group is given as input, the construction of the graph of groups is in NP and, consequently, the isomorphism problem in PSPACE. While the algorithm itself is rather simple and uses only standard tools from formal language theory, its proof of correctness is more geometric and makes use of the structure tree theory introduced by Dicks and Dunwoody. This talk is based on joint work with Geraud Senizergues.