A1 Refereed original research article in a scientific journal

One-Variable Word Equations and Three-Variable Constant-Free Word Equations




AuthorsNowotka D, Saarela A

PublisherWORLD SCIENTIFIC PUBL CO PTE LTD

Publication year2018

JournalInternational Journal of Foundations of Computer Science

Journal name in sourceINTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Journal acronymINT J FOUND COMPUT S

Volume29

Issue05

First page 935

Last page950

Number of pages16

ISSN0129-0541

eISSN1793-6373

DOIhttps://doi.org/10.1142/S0129054118420121

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/35741481


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 2024-26-11 at 14:13