×

Remarks on privileged words. (English) Zbl 1353.68223

Privileged words can be defined recursively as follows: a) the empty word and letters are privileged, b) words with the same privileged prefix and suffix with no other occurrences are privileged.
The paper contains the following results:
\(\bullet\) if a power \(w^i\) of the word \(w\) for some \(i\geq 1\) is privileged, then it is privileged for all \(i\geq 0\),
\(\bullet\) the language of all privileged words over a given alphabet is not context-free,
\(\bullet\) a linear-time algorithm is given to check if a word is privileged or not,
\(\bullet\) the number \(B(n)\) of length-\(n\) privileged binary words is at least \(2^{n-4}/n^2\).
The open problem “What is the true asymptotic behavior of \(B(n)\) as \(n \rightarrow \infty \)” is exposed.

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] DOI: 10.1007/978-3-319-15579-1_29 · Zbl 1451.68211 · doi:10.1007/978-3-319-15579-1_29
[2] DOI: 10.1016/j.aam.2013.01.002 · Zbl 1285.68133 · doi:10.1016/j.aam.2013.01.002
[3] DOI: 10.1016/j.disc.2013.08.026 · Zbl 1344.68179 · doi:10.1016/j.disc.2013.08.026
[4] DOI: 10.1137/0206024 · Zbl 0372.68005 · doi:10.1137/0206024
[5] DOI: 10.1007/BF01694004 · Zbl 0175.27802 · doi:10.1007/BF01694004
[6] DOI: 10.1016/j.tcs.2013.05.028 · Zbl 1296.68119 · doi:10.1016/j.tcs.2013.05.028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.