One-Variable Word Equations and Three-Variable Constant-Free Word Equations
Dirk Nowotka, Aleksi Saarela · International Journal of Foundations of Computer Science · 2018
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 [Formula: see text] such that every one-variable equation has either infinitely many solutions or at most [Formula: see text]. The second conjecture claims that there is a constant [Formula: see text] such that every independent system of three-variable constant-free equations with a nonperiodic solution is of size at most [Formula: see text]. We prove that the first conjecture implies the second one, possibly for a different constant.