• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

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

Juhani Karhumäki, Aleksi Saarela, An Analysis and a Reproof of Hmelevskii's Theorem (Extended Abstract). In: Masami Ito, Masafumi Toyama (Eds.), Developments in Language Theory, Lecture Notes in Computer Science 5257, 467–478, Springer, 2008.

Abstract:

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.

BibTeX entry:

@INPROCEEDINGS{inpKaSa08a,
  title = {An Analysis and a Reproof of Hmelevskii's Theorem (Extended Abstract)},
  booktitle = {Developments in Language Theory},
  author = {Karhumäki, Juhani and Saarela, Aleksi},
  volume = {5257},
  series = {Lecture Notes in Computer Science},
  editor = {Ito, Masami and Toyama, Masafumi},
  publisher = {Springer},
  pages = {467–478},
  year = {2008},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication