A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Remarks on privileged words
Tekijät: Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, Jeffrey Shallit
Julkaisuvuosi: 2016
Journal: International Journal of Foundations of Computer Science
Vuosikerta: 27
Numero: 4
Aloitussivu: 431
Lopetussivu: 442
Sivujen määrä: 12
ISSN: 0129-0541
DOI: https://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$.