A4 Article in conference proceedings

An optimal bound on the solution sets of one-variable word equations and its consequences

List of Authors: Nowotka Dirk, Saarela Aleksi

Conference name: International Colloquium on Automata, Languages and Programming

Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Publication year: 2018

Journal: LIPICS – Leibniz international proceedings in informatics

Book title *: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Journal name in source: Leibniz International Proceedings in Informatics, LIPIcs

Title of series: LIPIcs: Leibniz International Proceedings in Informatics

Volume number: 107

ISBN: 978-3-95977-076-7

ISSN: 1868-8969

DOI: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.136

URL: http://drops.dagstuhl.de/opus/volltexte/2018/9140

We solve two long-standing open problems on word equations. Firstly, we prove that a onevariable 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.

Downloadable publication This is an electronic reprint of the original article. |