Mhaskar Neerja and Michael Soltys

**Forced Repetitions over Alphabet Lists**

Abstract: |

Thue (1906) showed that there exist arbitrarily long
square-free strings over an alphabet of three symbols (not true for
two symbols). An open problem was posed
in Grytczuk et al. (2010), which is a generalization of Thue's original
result: given an alphabet list L=L, . . ., _{1}L$, where |_{}nL|=3$, is
it always possible to find a square-free string,
_{i}=ww_{1} ⸳ ⸳ ⸳ w_{2}, where w_{n} ∈ w_{i}L? In this paper we show that squares can be forced on square-free strings over alphabet lists iff a suffix of the square-free string conforms to a pattern which we term as an offending suffix. We also prove properties of offending suffixes. However, the problem remains tantalizingly open.
_{i} |

Download paper: | |||

PostScript | BibTeX reference |

Download presentation: |