2015/08/10 by Ciobanu, Laura, Diekert, Volker, Elder, Murray · 1 citation
#03D05 #20F65 #20F70 #68Q25 #68Q45 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.1508.02149
We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set of all solutions in reduced words is an indexed language in the sense of Aho. The language characterization we give, as well as further questions about the existence or finiteness of solutions, follow from our explicit construction of a finite directed graph which encodes all the solutions. Our result incorporates the recently invented recompression technique of Jeż, and a new way to integrate solutions of linear Diophantine equations into the process. As a byproduct of our techniques, we improve the complexity from quadratic nondeterministic space in previous works to NSPACE(nlog n) here.