An Improved Version of Hmelevskii's Theorem on Three-Variable Word Equations;
: Saarela, Aleksi
: Mahajan, Meena; Manea, Florin; McIver, Annabelle; Thắng, Nguyễn Kim
: Symposium on Theoretical Aspects of Computer Science
: 2026
LIPICS – Leibniz International Proceedings in Informatics
: 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)
: 77
: 364
: 978-3-95977-412-3
: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.STACS.2026.77
: https://doi.org/10.4230/LIPIcs.STACS.2026.77
: https://research.utu.fi/converis/portal/detail/Publication/526554894
Hmelevskii proved in 1971 that every constant-free three-variable word equation has a parametric solution. We prove an improved version of this result by showing that every such equation has a parametric solution using only three numerical parameters and with only two levels of nesting. This means that the structure of the solution sets of these equations is considerably simpler than has been known before.
parametric word, Word equation
:
Supported by the Research Council of Finland under grant 339311.
