A4 Refereed article in a conference publication
One-unknown word equations and three-unknown constant-free word equations
Authors: Dirk Nowotka, Aleksi Saarela
Editors: Srečko Brlek, Christophe Reutenauer
Conference name: International Conference on Developments in Language Theory
Publication year: 2016
Book title : Developments in Language Theory: 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings
Series title: Lecture Notes in Computer Science
Number in series: 9840
Volume: 9840
First page : 332
Last page: 343
Number of pages: 12
ISBN: 978-3-662-53131-0
eISBN: 978-3-662-53132-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-662-53132-7_27
We prove connections between one-unknown word equations and
three-unknown constant-free word equations, and use them to prove that
the number of equations in an independent system of three-unknown
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-unknown 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-unknown 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.
Downloadable publication This is an electronic reprint of the original article. |  |
