A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Remarks on privileged words




Julkaisun tekijät: Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, Jeffrey Shallit
Julkaisuvuosi: 2016
Journal: International Journal of Foundations of Computer Science
Volyymi: 27
Julkaisunumero: 4
Sivujen määrä: 12
ISSN: 0129-0541

Tiivistelmä

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



Sisäiset tekijät/toimittajat

Last updated on 2019-11-09 at 21:12