ON SOME PROPERTIES OF THE LANGUAGE OF 2-COLLAPSING WORDS
Elena V. Pribavkina · International Journal of Foundations of Computer Science · 2006
We present two new results on 2-collapsing words. First, we show that the language of all 2-collapsing words over 2 letters is not context-free. Second, we prove that the length of a 2-collapsing word over an arbitrary finite alphabet Σ is at least 2|Σ|2 thus improving the previously known lower bound |Σ|2 + 1.