2013/11/28 by Michael Forsyth, Forsyth, Michael, Amlesh Jayakumar +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.DM #cs.FL #math.CO
paper · pdf · doi:10.48550/arxiv.1311.7403
arxiv created 2013/11/28 · arxiv updated 2013/12/02
We discuss the notion of privileged word, recently introduced by Peltomaki. A word w is privileged if it is of length <=1, or has a privileged border that occurs exactly twice in w. We prove the following results: (1) if wk is privileged for some k >=1, then wj is privileged for all j >= 0; (2) the language of privileged words is neither regular nor context-free; (3) there is a linear-time algorithm to check if a given word is privileged; and (4) there are at least 2n-5/n2 privileged binary words of length n.