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: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |