A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Remarks on privileged words




TekijätMichael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, Jeffrey Shallit

Julkaisuvuosi2016

JournalInternational Journal of Foundations of Computer Science

Vuosikerta27

Numero4

Aloitussivu431

Lopetussivu442

Sivujen määrä12

ISSN0129-0541

DOIhttps://doi.org/10.1142/S0129054116500088


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



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