- Title
- Solution sets for equations over free groups are EDT0L languages
- Creator
- Ciobanu, Laura; Diekert, Volker; Elder, Murray
- Relation
- International Journal of Algebra and Computation Vol. 26, Issue 5, p. 843-886
- Publisher Link
- http://dx.doi.org/10.1142/S0218196716500363
- Publisher
- World Scientific Publishing
- Resource Type
- journal article
- Date
- 2016
- Description
- 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 Jez, 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(nlogn) here.
- Subject
- equation in a free group; EDT0L language; indexed language; compression; free monoid with involution
- Identifier
- http://hdl.handle.net/1959.13/1322818
- Identifier
- uon:24664
- Identifier
- ISSN:0218-1967
- Rights
- Electronic version of an article published as International Journal of Algebra and Computation Vol. 26, Issue 5, p. 843-886 (2016) http://dx.doi.org/10.1142/S0218196716500363© World Scientific Publishing Company http://www.worldscientific.com/worldscinet/ijac
- Language
- eng
- Full Text
- Reviewed
- Hits: 695
- Visitors: 965
- Downloads: 197
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 607 KB | Adobe Acrobat PDF | View Details Download |