Remarks on privileged words




Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, Jeffrey Shallit

2016

International Journal of Foundations of Computer Science

27

4

431

442

12

0129-0541

DOIhttps://doi.org/10.1142/S0129054116500088



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$.



Last updated on 2024-26-11 at 21:17