Solutions to twisted word equations and equations in virtually free groups

Diekert, V; Elder, M

Solutions to twisted word equations and equations in virtually free groups

Diekert, V Elder, M

Permalink

Publisher:: World Scientific Pub Co Pte Lt
Publication Type:: Journal Article
Citation:: International Journal of Algebra and Computation, pp. 1 - 89

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (790.93 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Diekert, V	en_US
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.date.accessioned	2020-04-18T02:46:57Z
dc.date.available	2021-02-20T18:05:52Z
dc.identifier.citation	International Journal of Algebra and Computation, pp. 1 - 89	en_US
dc.identifier.issn	0218-1967	en_US
dc.identifier.uri	http://hdl.handle.net/10453/140082
dc.description.abstract	<jats:p> It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper, we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in [Formula: see text]. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in [Formula: see text] an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or “small enough”) finite monoid, then our algorithms can be implemented in [Formula: see text], that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and Sénizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions. </jats:p>	en_US
dc.language	en	en_US
dc.publisher	World Scientific Pub Co Pte Lt	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.hasversion	Accepted Manuscript Version	en_US
dc.relation.isbasedon	10.1142/s0218196720500198	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.subject.classification	General Mathematics	en_US
dc.title	Solutions to twisted word equations and equations in virtually free groups	en_US
dc.type	Journal Article
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.publication-status	Published online	en_US

Abstract:

It is well known that the problem solving equations in virtually free groups can be reduced to the problem of solving twisted word equations with regular constraints over free monoids with involution. In this paper, we prove that the set of all solutions of a twisted word equation is an EDT0L language whose specification can be computed in [Formula: see text]. Within the same complexity bound we can decide whether the solution set is empty, finite, or infinite. In the second part of the paper we apply the results for twisted equations to obtain in [Formula: see text] an EDT0L description of the solution set of equations with rational constraints for finitely generated virtually free groups in standard normal forms with respect to a natural set of generators. If the rational constraints are given by a homomorphism into a fixed (or “small enough”) finite monoid, then our algorithms can be implemented in [Formula: see text], that is, in quasi-quadratic nondeterministic space. Our results generalize the work by Lohrey and Sénizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to both complexity and expressive power. Neither paper gave any concrete complexity bound and the results in these papers are stated for subsets of solutions only, whereas our results concern all solutions.

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

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