You are here: TUCS > PUBLICATIONS > Publication Search > On the Equation xk
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
On the Equation xk = z1k1z2k2…znkn in a Free Semigroup
Tero Harju, Dirk Nowotka, On the Equation <i>x<sup>k</sup></i> = <i>z</i><sub>1</sub><sup><i>k</i><sub>1</sub></sup><i>z</i><sub>2</sub><sup><i>k</i><sub>2</sub></sup>…<i>z</i><sub><i>n</i></sub><sup><i>k</i><sub><i>n</i></sub></sup> in a Free Semigroup. TUCS Technical Reports 602, Turku Centre for Computer Science, 2004.
Abstract:
Word equations of the form
<i>x<sup>k</sup></i> = <i>z</i><sub>1</sub><sup><i>k</i><sub>1</sub></sup><i>z</i><sub>2</sub><sup><i>k</i><sub>2</sub></sup>...<i>z</i><sub><i>n</i></sub><sup><i>k</i><sub><i>n</i></sub></sup>
are considered in this paper. In particular, we investigate
the case where <i>x</i> is of different length than <i>z<sub>i</sub></i>,
for any <i>i</i>,
and <i>k</i> and <i>k<sub>i</sub></i> are at least 3,
for all 1 ≤ <i>i</i> ≤ <i>n</i>, and <i>n</i> ≤ <i>k</i>.
We prove that for those equations all solutions are of rank 1, that is,
<i>x</i> and <i>z<sub>i</sub></i> are powers of the same word for all
1 ≤ <i>i</i> ≤ <i>n</i>.
It is also shown that this result implies a well-known result
by K.I. Appel and F.M. Djorup about the more special case
where <i>k<sub>i</sub></i> = <i>k<sub>j</sub></i>
for all 1 ≤ <i>i</i> < <i>j</i> ≤ <i>n</i>.
Files:
Abstract in PDF-formatBibTeX entry:
@TECHREPORT{tHaNo04a,
title = {On the Equation xk = z1k1z2k2…znkn in a Free Semigroup},
author = {Harju, Tero and Nowotka, Dirk},
number = {602},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2004},
keywords = {combinatorics on words, word equations},
ISBN = {952-12-1342-6},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics