A1 Refereed original research article in a scientific journal

An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences



Authors: Nowotka Dirk, Saarela Aleksi

Publisher: SIAM PUBLICATIONS

Publication year: 2022

Journal: SIAM Journal on Computing

Journal name in source: SIAM JOURNAL ON COMPUTING

Journal acronym: SIAM J COMPUT

Volume: 51

Issue: 1

First page : 1

Last page: 18

Number of pages: 18

ISSN: 0097-5397

DOI: https://doi.org/10.1137/20M1310448

Web address : https://doi.org/10.1137/20M1310448

Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/174890785


Abstract
We solve two long-standing open problems on word equations. Firstly, we prove that a one-variable word equation with constants has either at most three or an infinite number of solutions. The existence of such a bound had been conjectured, and the bound three is optimal. Secondly, we consider independent systems of three-variable word equations without constants. If such a system has a nonperiodic solution, then this system has at most 17 equations. Although probably not optimal, this is the first finite bound found. However, the conjecture of that bound being actually two still remains open.

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 20:19