A1 Journal article – refereed
One-Variable Word Equations and Three-Variable Constant-Free Word Equations




List of Authors: Nowotka D, Saarela A
Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD
Publication year: 2018
Journal: International Journal of Foundations of Computer Science
Journal name in source: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Journal acronym: INT J FOUND COMPUT S
Volume number: 29
Issue number: 05
Number of pages: 16
ISSN: 0129-0541
eISSN: 1793-6373

Abstract
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.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




Last updated on 2019-29-01 at 16:55