Solutions of twisted word equations, EDT0L languages, and context-free groups

Diekert, V; Elder, M

Solutions of twisted word equations, EDT0L languages, and context-free groups

Diekert, V Elder, M

Permalink

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

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (573.58 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.issued	2017-07-01	en_US
dc.identifier.citation	Leibniz International Proceedings in Informatics, LIPIcs, 2017, 80	en_US
dc.identifier.isbn	9783959770415	en_US
dc.identifier.issn	1868-8969	en_US
dc.identifier.uri	http://hdl.handle.net/10453/110193
dc.description.abstract	© Volker Diekert and Murray Elder; 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems, F.4.2 Grammars and Other Rewriting Systems, F.4.3 Formal Languages. We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational constraints in a contextfree group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Sénizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the "optimal" formal language characterization.	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.2017.96	en_US
dc.title	Solutions of twisted word equations, EDT0L languages, and context-free groups	en_US
dc.type	Conference Proceeding
utslib.citation.volume	80	en_US
utslib.for	0804 Data Format	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	80	en_US

Abstract:

© Volker Diekert and Murray Elder; 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems, F.4.2 Grammars and Other Rewriting Systems, F.4.3 Formal Languages. We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational constraints in a contextfree group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Sénizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the "optimal" formal language characterization.

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

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