Maximal State Complexity and Generalized de Bruijn Words

DOI10.1016/J.IC.2021.104689arXiv1903.05442MaRDI QIDQ6315528FDOQ6315528

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

Publication date: 13 March 2019

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.

Mathematics Subject Classification ID

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

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)