On the state complexity of partial word DFAs

Recently, Dassow et al. connected partial words and regular languages. Partial words are sequences in which some positions may be undefined, represented with a “hole” symbol ⋄. If we restrict what the symbol ⋄ can represent, we can use partial words to compress the representation of regular languages. Doing so allows the creation of so-called ⋄-DFAs, smaller than the DFAs recognizing the original language L, which recognize the compressed language. However, the ⋄-DFAs may be larger than the NFAs recognizing L. In this paper, we investigate a question of Dassow et al. as to how these sizes are related.