An Analysis and a Reproof of Hmelevskii's Theorem (Extended Abstract)



: Juhani Karhumäki, Aleksi Saarela

: Masami Ito, Masafumi Toyama

: 2008

Lecture Notes in Computer Science

: Developments in Language Theory

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS

: LECT NOTES COMPUT SC

: Lecture Notes in Computer Science

: 5257

: 467

: 478

: 12

: 978-3-540-85779-2

: 978-3-540-85780-8

: 0302-9743

DOI: https://doi.org/10.1007/978-3-540-85780-8_37


We analyze and reprove the famous theorem of Hmelevskii, which states that the general solutions of constant-free equations on three unknowns are finitely parameterizable, that is expressible by a finite collection of formulas of word and numerical parameters. The proof is written, and simplified, by using modern tools of combinatorics on words. As a new aspect the size of the finite representation is estimated, it is bounded by a double exponential function on the size of the equation.

Last updated on 2025-14-10 at 10:10