Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Remarks on Privileged Words

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