A4 Refereed article in a conference publication
An optimal bound on the solution sets of one-variable word equations and its consequences
Authors: Nowotka Dirk, Saarela Aleksi
Editors: Ioannis Chatzigiannakis, Christos Kaklamanis, Daniel Marx, Donald Sannella
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
Series title: LIPIcs: Leibniz International Proceedings in Informatics
Volume: 107
First page : 136:1
Last page: 136:13
ISBN: 978-3-95977-076-7
ISSN: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.ICALP.2018.136
Web address : http://drops.dagstuhl.de/opus/volltexte/2018/9140
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/35729244
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. |  |
