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

The Non-Parametrizability of the Word Equation xyz=zvx: A Short Proof

Elena Czeizler, The Non-Parametrizability of the Word Equation xyz=zvx: A Short Proof. Theoretical Computer Science 345(2-3), 296–303, 2005.

Abstract:

Although Makanin proved the problem of satisfiability of word
equations to be decidable, the general structure of solutions is
difficult to describe. In particular, Hmelevskii proved that the
set of solutions of $xyz=zvx$ cannot be described using only
finitely many parameters, contrary to the case of equations in
three unknowns. In this paper we give a short, elementary proof of
Hmelevkii's result.

BibTeX entry:

@ARTICLE{jCzeizler05a,
  title = {The Non-Parametrizability of the Word Equation xyz=zvx: A Short Proof},
  author = {Czeizler, Elena},
  journal = {Theoretical Computer Science},
  volume = {345},
  number = {2-3},
  pages = {296–303},
  year = {2005},
}

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

Publication Forum rating of this publication: level 2

Edit publication