A4 Refereed article in a conference publication
On the Complexity of Hmelevskii's Theorem and Satisfiability of Three Unknown Equations
Authors: Saarela Aleksi
Editors: Volker Diekert, Dirk Nowotka
Conference name: International Conference on Developments in Language Theory
Publication year: 2009
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: 5583
First page : 443
Last page: 453
Number of pages: 11
ISBN: 978-3-642-02736-9
eISBN: 978-3-642-02737-6
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-02737-6_36
We analyze Hmelevskii's theorem, which states that the general solutions of constant-free equations on three unknowns are expressible by a finite collection of formulas of word and numerical parameters. We prove that the size of the finite representation is bounded by an exponential function on the size of the equation. We also prove that the shortest nontrivial solution of the equation, if it exists, is exponential, and that its existence can be solved in nondeterministic polynomial time.
Downloadable publication This is an electronic reprint of the original article. |  |
