A1 Refereed original research article in a scientific journal
On the Solution Sets of Three-Variable Word Equations
Authors: Saarela, Aleksi
Publisher: SPRINGER
Publishing place: NEW YORK
Publication year: 2024
Journal: Theory of Computing Systems
Journal name in source: THEORY OF COMPUTING SYSTEMS
Journal acronym: THEOR COMPUT SYST
Volume: 68
Issue: 6
First page : 1556
Last page: 1571
Number of pages: 16
ISSN: 1432-4350
eISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-024-10193-9
Web address : https://doi.org/10.1007/s00224-024-10193-9
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/457699339
It is known that the set of solutions of any constant-free three-variable word equation can be represented using parametric words, and the number of numerical parameters and the level of nesting in these parametric words is at most logarithmic with respect to the length of the equation. We show that this result can be significantly improved in the case of unbalanced equations, that is, equations where at least one variable has a different number of occurrences on the left-hand side and on the right-hand side. More specifically, it is sufficient to have two numerical parameters and one level of nesting in this case. We also discuss the possibility of proving a similar result for balanced equations in the future.
Downloadable publication This is an electronic reprint of the original article. |  |
Funding information in the publication:
Open Access funding provided by University of Turku (including Turku University Central Hospital).
