2018/02/20 by Sénizergues, Géraud, Weiß, Armin
#05C25 #20E08 #20F10 #20F65 #68Q25 #68Q45 #Computational Complexity (cs.CC) #F.2.2 #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #G.2.2 #Group Theory (math.GR)
paper · doi:10.48550/arxiv.1802.07085
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 G with finite vertex groups and fundamental group G. Our algorithm is non-deterministic and runs in doubly exponential time. 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.