A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences
Tekijät: Nowotka Dirk, Saarela Aleksi
Kustantaja: SIAM PUBLICATIONS
Julkaisuvuosi: 2022
Journal: SIAM Journal on Computing
Tietokannassa oleva lehden nimi: SIAM JOURNAL ON COMPUTING
Lehden akronyymi: SIAM J COMPUT
Vuosikerta: 51
Numero: 1
Aloitussivu: 1
Lopetussivu: 18
Sivujen määrä: 18
ISSN: 0097-5397
DOI: https://doi.org/10.1137/20M1310448
Verkko-osoite: https://doi.org/10.1137/20M1310448
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/174890785
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 has at most 17 equations. 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. |  |
