20
$\begingroup$

Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for some string $\gamma$.

Now, my question is whether the following holds:

For every $\Sigma$, there exists some $n \in \mathbb{N}$ such that for every string $\alpha$ over $\Sigma$ of length at least $n$, $\alpha$ contains at least one repeat.

I've checked this over the binary alphabet, and this is quite easy for that case, but an alphabet of size 3 is already quite a bit harder to check, amd I'd like a proof for arbitrarily large grammars.

If the above conjecture is true, then I can (almost) remove the demand for inserting empty strings in my other question.

$\endgroup$
15
$\begingroup$

No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols.

This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance:

  • $\{xyyz \mid x,y,z\in \Sigma^+\}$ is co-finite for $|\Sigma|\leq 2$ but not context-free for $\Sigma>2$.
  • The class of languages generated by terminal-free patterns can be learned in the limit if $|\Sigma|>3$ but not so if $|\Sigma|=2$ [Reid2004].
$\endgroup$
  • $\begingroup$ Damn, that's too bad then :S $\endgroup$ – Alex ten Brink Mar 25 '12 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.