Prague Stringology Conference 2016

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=L1, . . ., Ln$, where |Li|=3$, is it always possible to find a square-free string, w=w1w2 ⸳ ⸳ ⸳ wn, where wi ∈ Li? 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.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation