A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
An optimal bound on the solution sets of one-variable word equations and its consequences
Tekijät: Nowotka Dirk, Saarela Aleksi
Toimittaja: Ioannis Chatzigiannakis, Christos Kaklamanis, Daniel Marx, Donald Sannella
Konferenssin vakiintunut nimi: International Colloquium on Automata, Languages and Programming
Kustantaja: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Julkaisuvuosi: 2018
Journal: LIPICS – Leibniz international proceedings in informatics
Kokoomateoksen nimi: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Tietokannassa oleva lehden nimi: Leibniz International Proceedings in Informatics, LIPIcs
Sarjan nimi: LIPIcs: Leibniz International Proceedings in Informatics
Vuosikerta: 107
Aloitussivu: 136:1
Lopetussivu: 136:13
ISBN: 978-3-95977-076-7
ISSN: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.ICALP.2018.136
Verkko-osoite: http://drops.dagstuhl.de/opus/volltexte/2018/9140
Rinnakkaistallenteen osoite: 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
