A word is said to be primitive if it cannot be expressed as non-trivial power of another word. We characterize a class of primitive words, referred as del-robust primitive words, which remain primitive on deletion of any letter. It is also shown that the language of primitive words that are not del-robust is not context-free. Finally, we present a linear time algorithm to recognize del-robust primitive words and give a lower bound on the number of n -length del-robust primitive words.
['Amit Kumar Srivastava', 'Ananda Chandra Nayak', 'Kalpesh Kapoor']
On del-robust primitive words