License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.96
URN: urn:nbn:de:0030-drops-73976
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7397/
Go to the corresponding LIPIcs Volume Portal

Diekert, Volker ; Elder, Murray

Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

pdf-format:
LIPIcs-ICALP-2017-96.pdf (0.6 MB)

Abstract

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 context-free 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 Senizergues (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.

BibTeX - Entry

@InProceedings{diekert_et_al:LIPIcs:2017:7397,
  author =	{Volker Diekert and Murray Elder},
  title =	{{Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{96:1--96:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7397},
  URN =		{urn:nbn:de:0030-drops-73976},
  doi =		{10.4230/LIPIcs.ICALP.2017.96},
  annote =	{Keywords: Twisted word equation, EDT0L, virtually free group, context-free group}
}

Keywords: Twisted word equation, EDT0L, virtually free group, context-free group
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI