Maximal state complexity and generalized de Bruijn words

Abstrakt

We compute the exact maximum state complexity for the language consisting of m words of length N, and characterize languages achieving the maximum. We also consider a special case, namely languages C(w) consisting of the conjugates of a single word w.

The words for which the maximum state complexity of C(w) is achieved turn out to be a natural generalization of de Bruijn words. We show that generalized de Bruijn words exist for each length and consider the number of them.& nbsp;(c) 2021 Elsevier Inc.

All rights reserved.

Klíčová slova

• number