A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
On the Complexity of Hmelevskii's Theorem and Satisfiability of Three Unknown Equations
Tekijät: Saarela Aleksi
Toimittaja: Volker Diekert, Dirk Nowotka
Konferenssin vakiintunut nimi: International Conference on Developments in Language Theory
Julkaisuvuosi: 2009
Journal: 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: 5583
Aloitussivu: 443
Lopetussivu: 453
Sivujen määrä: 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
