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

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

Aleksi Saarela, On the Complexity of Hmelevskii's Theorem and Satisfiability of Three Unknown Equations. In: Volker Nowotka Dirk Diekert (Ed.), Proceedings of the 13th International Conference on Developments in Language Theory, 5583, 443-453, Springer, 2009.

Abstract:

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.

BibTeX entry:

@INPROCEEDINGS{inpSaarela09a,
  title = {On the Complexity of Hmelevskii's Theorem and Satisfiability of Three Unknown Equations},
  booktitle = {Proceedings of the 13th International Conference on Developments in Language Theory},
  author = {Saarela, Aleksi},
  volume = {5583},
  editor = {Diekert, Volker Nowotka Dirk},
  publisher = {Springer},
  pages = {443-453},
  year = {2009},
}

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

Edit publication