Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Word Equations with One Unknow...

Word Equations with One Unknown

Markku Laine, Wojciech Plandowski, Word Equations with One Unknown . In: Volker Diekert, Dirk Nowotka (Eds.), Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings., Lecture Notes in Computer Science 5583, 348-359, Springer, 2009.

Abstract:

We consider properties of the solution set of a word equation
with one unknown. We prove that the solution set of a word equation
possessing infinite number of solutions is of the form (pq)^*p where pq
is primitive. Next, we prove that a word equation with at most four
occurrences of the unknown possesses either infinitely many solutions
or at most two solutions. We show that there are equations with at
most four occurrences of the unknown possessing exactly two solutions.
Finally, we prove that a word equation with at most 2k occurrences
of the unknown possesses either infinitely many solutions or at most
8 log k + O(1) solutions. Hence, if we consider a class E_k of equations
with at most 2k occurrences of the unknown, then each equation in this
class possesses either infinitely many solutions or a constant number of
solutions. Our considerations allow to construct the first truly linear time
algorithm for computing the solution set of an equation in a nontrivial
class of equations.

BibTeX entry:

@INPROCEEDINGS{inpLaPl09a,
  title = {Word Equations with One Unknown },
  booktitle = {Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings.},
  author = {Laine, Markku and Plandowski, Wojciech},
  volume = {Lecture Notes in Computer Science 5583},
  editor = {Diekert, Volker and Nowotka, Dirk},
  publisher = {Springer},
  pages = {348-359},
  year = {2009},
  keywords = {combinatorics on words, word equations},
}

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

Edit publication