A4 Refereed article in a conference publication
An Improved Version of Hmelevskii's Theorem on Three-Variable Word Equations; 
Authors: Saarela, Aleksi
Editors: Mahajan, Meena; Manea, Florin; McIver, Annabelle; Thắng, Nguyễn Kim
Conference name: Symposium on Theoretical Aspects of Computer Science
Publication year: 2026
Journal: LIPICS – Leibniz International Proceedings in Informatics
Book title : 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)
Article number: 77
Volume: 364
ISBN: 978-3-95977-412-3
eISSN: 1868-8969
DOI: https://doi.org/10.4230/LIPIcs.STACS.2026.77
Publication's open availability at the time of reporting: Open Access
Publication channel's open availability : Open Access publication channel
Web address : https://doi.org/10.4230/LIPIcs.STACS.2026.77
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/526554894
Self-archived copy's licence: CC BY
Self-archived copy's version: Publisher`s PDF
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.
Keywords:
parametric word, Word equation
Downloadable publication This is an electronic reprint of the original article. |  |
Funding information in the publication:
Supported by the Research Council of Finland under grant 339311.
