Solution sets for equations over free groups are EDT0L languages
Authors:
Preprint
Abstract
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. Thus, for each equation there is a construction of a Lindenmayer system which generates all solutions in reduced words. 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\.z, 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 quasi-linear nondeterministic space here.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- More Than 1700 Years of Word Equations2015
- Word-Mappings of Level 2Theory of Computing Systems, 2013
- The equation w(x, y) = u over free groups: an algebraic approachJournal of Group Theory, 2009
- Elementary theory of free non-abelian groupsJournal of Algebra, 2006
- An efficient algorithm for solving word equations2006
- The Book of Traces1995
- ON SYSTEMS OF EQUATIONS IN A FREE GROUPMathematics of the USSR-Izvestiya, 1985
- Partial commutations and faithful rational transductionsTheoretical Computer Science, 1984
- Parallel Program Schemata and Maximal Parallelism I. Fundamental ResultsJournal of the ACM, 1973
- Indexed Grammars—An Extension of Context-Free GrammarsJournal of the ACM, 1968