A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
An Analysis and a Reproof of Hmelevskii's Theorem (Extended Abstract)
Tekijät: Juhani Karhumäki, Aleksi Saarela
Toimittaja: Masami Ito, Masafumi Toyama
Julkaisuvuosi: 2008
Lehti:: Lecture Notes in Computer Science
Kokoomateoksen nimi: Developments in Language Theory
Tietokannassa oleva lehden nimi: DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS
Lehden akronyymi: LECT NOTES COMPUT SC
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 5257
Aloitussivu: 467
Lopetussivu: 478
Sivujen määrä: 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
