A1 Refereed original research article in a scientific journal

Remarks on privileged words




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

Publication year2016

JournalInternational Journal of Foundations of Computer Science

Volume27

Issue4

First page 431

Last page442

Number of pages12

ISSN0129-0541

DOIhttps://doi.org/10.1142/S0129054116500088(external)


Abstract

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