CLR cover
Previous problem

Problem 69: Perfect Words

Next problem

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