License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.30
URN: urn:nbn:de:0030-drops-136751
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13675/
Go to the corresponding LIPIcs Volume Portal

Ferens, Robert ; Jeż, Artur

Solving One Variable Word Equations in the Free Group in Cubic Time

pdf-format:
LIPIcs-STACS-2021-30.pdf (0.7 MB)

Abstract

A word equation with one variable in a free group is given as U = V, where both U and V are words over the alphabet of generators of the free group and X, X⁻¹, for a fixed variable X. An element of the free group is a solution when substituting it for X yields a true equality (interpreted in the free group) of left- and right-hand sides. It is known that the set of all solutions of a given word equation with one variable is a finite union of sets of the form {α wⁱ β : i ∈ ℤ}, where α, w, β are reduced words over the alphabet of generators, and a polynomial-time algorithm (of a high degree) computing this set is known. We provide a cubic time algorithm for this problem, which also shows that the set of solutions consists of at most a quadratic number of the above-mentioned sets. The algorithm uses only simple tools of word combinatorics and group theory and is simple to state. Its analysis is involved and focuses on the combinatorics of occurrences of powers of a word within a larger word.

BibTeX - Entry

@InProceedings{ferens_et_al:LIPIcs.STACS.2021.30,
  author =	{Ferens, Robert and Je\.{z}, Artur},
  title =	{{Solving One Variable Word Equations in the Free Group in Cubic Time}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13675},
  URN =		{urn:nbn:de:0030-drops-136751},
  doi =		{10.4230/LIPIcs.STACS.2021.30},
  annote =	{Keywords: Word equations, free group, one-variable equations}
}

Keywords: Word equations, free group, one-variable equations
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

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