Vi visar att, med ett ord ekvation över en ändligt genererad fri grupp, uppsättningen av alla lösningar i reducerade ord bildar ett EDT0L språk. I synnerhet är det ett indexerat språk i betydelsen Aho. Frågan om huruvida en beskrivning av lösningen sätter i reducerade ord som ett indexerat språk är möjligt har varit öppen under några år [9, 10], uppenbarligen utan mycket hopp om att ett positivt svar kunde hålla. Vårt svar går dock långt utöver: de är EDT0L, som är en lämplig underklass av indexerade språk. Vi kan dessutom hantera existentiell teori av ekvationer med rationella begränsningar i fria produkter 1≤i≤s Fi, där varje Fi är antingen en fri eller ändlig grupp, eller en fri monoid med involution. I samtliga fall är resultatet detsamma: uppsättningen av alla lösningar i reducerade ord är EDT0L. Detta var känt endast för kvadratiska ord ekvationer av [8], Vilket är ett mycket begränsat fall. Vårt allmänna resultat blev möjligt på grund av den senaste rekompression tekniken av Jeż. I detta papper använder vi en ny metod för att integrera lösningar av linjära Diofantine ekvationer i processen och få mer allmänna resultat än i det relaterade papper [5]. Vi förbättrar till exempel komplexiteten från kvadratiskt icke-deterministiskt utrymme i [5] till kvasilinjärt icke-deterministiskt utrymme här. Detta innebär en förbättrad komplexitet för att avgöra existentiella teorin om icke-abeliska fria grupper: NSPACE(n log n). Den förmodade komplexiteten är dock NP, men vi anser att våra resultat är optimala med avseende på rymdens komplexitet, oberoende av den förmodade NP.
Dessutom är nod av grafen härledd av REF en utökad ekvation som är ett element i en fri delvis pendlande monoid snarare än en ordekvation.
Solution sets for equations over free groups are EDT0L languages
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}