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.2018.136
URN: urn:nbn:de:0030-drops-91404
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9140/
Go to the corresponding LIPIcs Volume Portal

Nowotka, Dirk ; Saarela, Aleksi

An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences

pdf-format:
LIPIcs-ICALP-2018-136.pdf (0.4 MB)

Abstract

We solve two long-standing open problems on word equations. Firstly, we prove that a one-variable word equation with constants has either at most three or an infinite number of solutions. The existence of such a bound had been conjectured, and the bound three is optimal. Secondly, we consider independent systems of three-variable word equations without constants. If such a system has a nonperiodic solution, then this system of equations is at most of size 17. Although probably not optimal, this is the first finite bound found. However, the conjecture of that bound being actually two still remains open.

BibTeX - Entry

@InProceedings{nowotka_et_al:LIPIcs:2018:9140,
  author =	{Dirk Nowotka and Aleksi Saarela},
  title =	{{An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{136:1--136:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9140},
  URN =		{urn:nbn:de:0030-drops-91404},
  doi =		{10.4230/LIPIcs.ICALP.2018.136},
  annote =	{Keywords: combinatorics on words, word equations, systems of equations}
}

Keywords: combinatorics on words, word equations, systems of equations
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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