## Remarks on Privileged Words

Michael Forsyth, Amlesh Jayakumar, Jarkko Peltomäki, Jeffrey Shallit, Remarks on Privileged Words. International Journal of Foundations of Computer Science 27(4), 431–442, 2016.

http://dx.doi.org/10.1142/S0129054116500088

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

### BibTeX entry:

@ARTICLE{jFoJaPeSh16a,  title = {Remarks on Privileged Words},  author = {Forsyth, Michael and Jayakumar, Amlesh and Peltomäki, Jarkko and Shallit, Jeffrey},  journal = {International Journal of Foundations of Computer Science},  volume = {27},  number = {4},  pages = {431–442},  year = {2016},  keywords = {privileged word,regular language,linear-time algorithm,context-free language,enumeration},  ISSN = {0129-0541},}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication