Solutions of twisted word equations, EDT0L languages, and context-free groups
Preprint
Abstract
We prove that the set of all solutions for twisted word equations with regular constraints is an EDT0L language and can be computed in PSPACE. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide (in PSPACE) whether or not the solution set is finite, which was an open problem. Our results generalize the work by Lohrey and S{\'e}nizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Neither paper gave any concrete complexity bound and both rely on the exponent of periodicity, so the result in these papers concern only subsets of solutions, whereas our results concern all solutions. We do more, we give, in some sense, the "optimal" formal language characterization of the full solution set.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Word-Mappings of Level 2Theory of Computing Systems, 2013
- A characterisation of virtually free groupsArchiv der Mathematik, 2007
- Elementary theory of free non-abelian groupsJournal of Algebra, 2006
- Logical aspects of Cayley-graphs: the group caseAnnals of Pure and Applied Logic, 2005
- The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete2001
- The accessibility of finitely presented groupsInventiones Mathematicae, 1985
- ON SYSTEMS OF EQUATIONS IN A FREE GROUPMathematics of the USSR-Izvestiya, 1985
- Groups, the Theory of ends, and context-free languagesJournal of Computer and System Sciences, 1983
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUPMathematics of the USSR-Sbornik, 1977
- Finite and infinite cyclic extensions of free groupsJournal of the Australian Mathematical Society, 1973