ON NON-PRIMITIVE PALINDROMIC CONTEXT-FREE LANGUAGES
Szilárd Zsolt Fazekas, Peter Leupold, Kayoko Shikishima-Tsuji · International Journal of Foundations of Computer Science · 2012
This work continues investigations on avoidability of languages. We show that the language of primitive non-palindromes is strongly unavoidable for context-free languages that are not linear. This means that every language from this class contains infinitely many primitive non-palindromes. In the second part, we extend the defintion of palindromes. In the center of a word we admit a bounded factor that is not palindromic. For k-palindromes, the length of this factor can be up to k. For non-primitive words, k-palindromicity implies conventional palindromicity if these words are long enough. Therefore we can extend the unavoidability result to k-palindromes.