2026-07-23T20:14:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25566 2026-03-19T13:35:06Z ddc:004 open_access

An Improved Version of Hmelevskii’s Theorem on Three-Variable Word Equations Saarela, Aleksi Combinatorics on words word equation parametric word 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksi Saarela 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.77 urn:nbn:de:0030-drops-255664 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.77 eng https://creativecommons.org/licenses/by/4.0/legalcode