A4 Refereed article in a conference publication
An Analysis and a Reproof of Hmelevskii's Theorem (Extended Abstract)
Authors: Juhani Karhumäki, Aleksi Saarela
Editors: Masami Ito, Masafumi Toyama
Publication year: 2008
Journal:: Lecture Notes in Computer Science
Book title : Developments in Language Theory
Journal name in source: DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS
Journal acronym: LECT NOTES COMPUT SC
Series title: Lecture Notes in Computer Science
Volume: 5257
First page : 467
Last page: 478
Number of pages: 12
ISBN: 978-3-540-85779-2
eISBN: 978-3-540-85780-8
ISSN: 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.
Downloadable publication This is an electronic reprint of the original article. |  |
