Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} $

The word $\sa{0110}$ is dense but $\sa{0101}$ is not. The longest binary perfect words are $\sa{011001010}$ and its complement $\sa{100110101}$, they have length $9$. However, on the ternary alphabet the word $\sa{0120022110}$ of length $10$ is perfect.

Problem 69: Perfect Words

A word of length is called dense if it has the largest number of (distinct) factors among words of the same length on the same alphabet. A word is said to be perfect if all its prefixes are dense. Note that each prefix of a perfect word is also perfect.

There are only finitely many binary perfect words, but the situation changes dramatically for larger alphabets.

Show how to construct in linear time a ternary perfect word of any given length. Prove also the existence of an infinite perfect ternary word.

Consider Hamiltonian and Eulerian cycles in de Bruijn automata.

References

D. Repke and W. Rytter. On semi-perfect de Bruijn words. Theor. Comput. Sci., 720:55-63, 2018.

N. Vörös. On the complexity measures of symbol-sequences. In A. Iványi, editor, Conference of Young Programmers and Mathematicians, pages 43-50, Budapest, 1984. Faculty of sciences, Eötvös Loránd University

125 Problems in Text Algorithms

Example

Problem 69: Perfect Words

References