Maximal State Complexity and Generalized de Bruijn Words

DOI10.1016/J.IC.2021.104689MaRDI QIDQ6315528arXivFDO

Authors Daniel Gabric, Štěpán Holub, Jeffrey Shallit

Publication date 13 March 2019

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: 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.

This page was built for publication: Maximal State Complexity and Generalized de Bruijn Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315528)