Remarks on Privileged Words
Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, Jeffrey Shallit · International Journal of Foundations of Computer Science · 2016
We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length ≤ 1, or has a privileged border that occurs exactly twice in w. We prove the following results: (1) if wk is privileged for some [Formula: see text], then wj is privileged for all [Formula: see text]; (2) the language of privileged words is not context-free; (3) there is a linear-time algorithm to check if a given word is privileged; and (4) there are at least [Formula: see text] privileged binary words of length n.