A1 Refereed original research article in a scientific journal
Remarks on privileged words
Authors: Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, Jeffrey Shallit
Publication year: 2016
Journal: International Journal of Foundations of Computer Science
Volume: 27
Issue: 4
First page : 431
Last page: 442
Number of pages: 12
ISSN: 0129-0541
DOI: https://doi.org/10.1142/S0129054116500088(external)
We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word $w$ is privileged if it is of length $leq 1$, or has a privileged border that occurs exactly twice in $w$. We prove the following results: (1) if $w^k$ is privileged for some $k geq 1$, then $w^j$ is privileged for all $j geq 0$; (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 $2^{n-4}/n^2$ privileged binary words of length $n$.