On the Complexity of Hmelevskii's Theorem and Satisfiability of Three Unknown Equations



: Saarela Aleksi

: Volker Diekert, Dirk Nowotka

: International Conference on Developments in Language Theory

: 2009

: Lecture Notes in Computer Science

: Developments in Language Theory

: DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS

: LECT NOTES COMPUT SC

: Lecture Notes in Computer Science

: 5583

: 443

: 453

: 11

: 978-3-642-02736-9

: 978-3-642-02737-6

: 0302-9743

DOI: https://doi.org/10.1007/978-3-642-02737-6_36(external)


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.

Last updated on 2024-26-11 at 10:24