Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please?

A word $w$ has a border $u$ if $u$ is both prefix and suffix of $w$ (and $u$ does not equal $\lambda$ or $w$).

  • 9
    $\begingroup$ can you define borderless words ? $\endgroup$ – Denis Jul 2 '13 at 10:26
  • 1
    $\begingroup$ What is $\lambda$? Ps., I think this is so trivial that it probably hasn't been published. $\endgroup$ – Pål GD Jul 2 '13 at 14:14
  • 4
    $\begingroup$ @PålGD $\lambda$ or $\varepsilon$ or $1$. PS. The language is not even context-free: arXiv:1008.2440 Theorem 7 $\endgroup$ – Hendrik Jan Jul 2 '13 at 14:26
  • $\begingroup$ @HendrikJan I think your answer is as good as any answer we can hope for for this question, so maybe you can just turn it into an answer? Also, maybe add that these words often are called bifix-free [Nielsen, 1973] and unbordered [your link]. $\endgroup$ – Pål GD Jul 3 '13 at 7:50

The borderless words are also known as unbordered or bifix-free ("A note on bifix-free sequences", PT Nielsen, in a paper as early as 1973).

The language of unbordered words is not even context-free, see the paper "Inverse star, borders, and palstars" by Ramparsad etal, in TCS with a preprint on ArXiv. The technique to obtain this result is Ogden's Lemma, an extension of classical pumping, and discussed elsewhere on this forum.


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.