State Complexity of Partial Word Finite Automata

Partial word finite automata are deterministic finite automata that may have state transitions on a special symbol lozenge which represents an unknown symbol or a hole in the word. Together with a subset of the input alphabet that gives the symbols which may be substituted for the lozenge, a partial word finite automaton represents a regular language. However, this substitution implies a certain form of limited nondeterminism in the computations when the lozenge-transitions are replaced by ordinary transitions. In this paper we first reconsider the problem to prove the minimality of partial word finite automata and present a method to utilize minimal NFAs with certain properties for this purpose. Then we study the operational state complexity of partial word finite automata with respect to Boolean operations. It turns out that the upper and lower bounds for all these operations are exponential. Moreover, we establish a state complexity hierarchy on the number of productive lozenge-transitions that may appear in partial word finite automata. The levels of the hierarchy are separated by exponential state costs.