Solution sets for equations over free groups are EDT0L languages

Ciobanu, L; Diekert, V; Elder, M

Solution sets for equations over free groups are EDT0L languages

Ciobanu, L Diekert, V Elder, M

Permalink

Publication Type:: Journal Article
Citation:: International Journal of Algebra and Computation, 2016, 26 (5), pp. 843 - 886
Issue Date:: 2016-08-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download full textAdobe PDF (528.72 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ciobanu, L	en_US
dc.contributor.author	Diekert, V	en_US
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.date.available	2020-05-25T19:22:16Z
dc.date.issued	2016-08-01	en_US
dc.identifier.citation	International Journal of Algebra and Computation, 2016, 26 (5), pp. 843 - 886	en_US
dc.identifier.issn	0218-1967	en_US
dc.identifier.uri	http://hdl.handle.net/10453/95781
dc.description.abstract	© World Scientific Publishing Company. 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(n log n) here.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP160100486
dc.relation.ispartof	International Journal of Algebra and Computation	en_US
dc.relation.isbasedon	10.1142/S0218196716500363	en_US
dc.subject.classification	General Mathematics	en_US
dc.title	Solution sets for equations over free groups are EDT0L languages	en_US
dc.type	Journal Article
utslib.citation.volume	5	en_US
utslib.citation.volume	26	en_US
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access
pubs.issue	5	en_US
pubs.publication-status	Published	en_US
pubs.volume	26	en_US

Abstract:

© World Scientific Publishing Company. 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(n log n) here.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/95781