Minimal Partial Languages and ◊-DFAs
Francine Blanchet-Sadri, Kira Goldner, and Aidan Shackleton

Abstract


Partial words are sequences of characters from an alphabet in which some positions may be marked with a “hole” symbol, ◊. We can create a ◊-substitution σ mapping this symbol into the alphabet, so that applying such a substitution to a partial word results in a set of “full” words (ones without holes). This setup allows us to compress regular languages into smaller partial languages. DFAs for such partial languages employ a limited non-determinism that can allow them to have lower state complexity than the minimal DFAs for the corresponding full languages. Our research focuses on algorithms for the creation of σ-minimal finite partial languages, approximation algorithms for the ◊-DFA minimization problem, and computational techniques for selecting optimal ◊-substitutions for a given full language.


Keywords

Combinatorics on Words; Partial Words; Regular Languages; DFAs; Partial Languages; ◊-DFAs; Complexity Theory.