Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Publication Type:
Conference Proceeding
Leibniz International Proceedings in Informatics (LIPIcs), 2017, 80 pp. 96:1 - 96:14
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
LIPIcs-ICALP-2017-96.pdfPublished version573.58 kB
Adobe PDF
We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. 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 whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the "optimal" formal language characterization.
Please use this identifier to cite or link to this item: