A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
One-Variable Word Equations and Three-Variable Constant-Free Word Equations
Tekijät: Nowotka D, Saarela A
Kustantaja: WORLD SCIENTIFIC PUBL CO PTE LTD
Julkaisuvuosi: 2018
Journal: International Journal of Foundations of Computer Science
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Lehden akronyymi: INT J FOUND COMPUT S
Vuosikerta: 29
Numero: 05
Aloitussivu: 935
Lopetussivu: 950
Sivujen määrä: 16
ISSN: 0129-0541
eISSN: 1793-6373
DOI: https://doi.org/10.1142/S0129054118420121
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/35741481
We prove connections between one-variable word equations and three-variable constant-free word equations, and use them to prove that the number of equations in an independent system of three-variable constant-free equations is at most logarithmic with respect to the length of the shortest equation in the system. We also study two well-known conjectures. The first conjecture claims that there is a constant c such that every one-variable equation has either infinitely many solutions or at most c. The second conjecture claims that there is a constant c such that every independent system of three-variable constant-free equations with a nonperiodic solution is of size at most c. We prove that the first conjecture implies the second one, possibly for a different constant.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
