Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE

Ciobanu, L; Elder, M

Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE

Ciobanu, L Elder, M

Permalink

Publication Type:: Conference Proceeding
Citation:: Leibniz International Proceedings in Informatics, LIPIcs, 2019, 132
Issue Date:: 2019-07-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (612.62 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ciobanu, L	en_US
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.date.available	2019-04-30	en_US
dc.date.issued	2019-07-01	en_US
dc.identifier.citation	Leibniz International Proceedings in Informatics, LIPIcs, 2019, 132	en_US
dc.identifier.isbn	9783959771092	en_US
dc.identifier.issn	1868-8969	en_US
dc.identifier.uri	http://hdl.handle.net/10453/133072
dc.description.abstract	© Laura Ciobanu and Murray Elder; licensed under Creative Commons License CC-BY We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in NSPACE(n2 log n) for the torsion-free case and NSPACE(n4 log n) for the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Jeż, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP160100486
dc.relation.ispartof	Leibniz International Proceedings in Informatics, LIPIcs	en_US
dc.relation.isbasedon	10.4230/LIPIcs.ICALP.2019.110	en_US
dc.title	Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE	en_US
dc.type	Conference Proceeding
utslib.citation.volume	132	en_US
utslib.for	0101 Pure 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.publication-status	Published	en_US
pubs.volume	132	en_US

Abstract:

© Laura Ciobanu and Murray Elder; licensed under Creative Commons License CC-BY We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in NSPACE(n2 log n) for the torsion-free case and NSPACE(n4 log n) for the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Jeż, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.

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

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