State Complexity of Partial Word Finite Automata
Martin Kutrib, Matthias Wendlandt · International Journal of Foundations of Computer Science · 2025
Partial word finite automata are deterministic finite automata that may have state transitions on a special symbol ◇ 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 ◇, a partial word finite automaton represents a regular language. However, this substitution implies a certain form of limited nondeterminism in the computations when the ◇-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 state complexity hierarchies on the number of productive ◇-transitions that may appear in partial word finite automata for general and unary regular languages. In the general case, the levels of the hierarchy are separated by exponential state costs, whereas in the unary case the levels are separated by quadratic state costs.