Determinization Complexities of ! Automata I
Yang Cai, Ting Zhang · 2013
Complementation and determinization are two fundamental notions in automata theory. The close relationship between the two has been well observed in the literature. In the case of nondeterministic nite automata on nite words (NFA), complementation and determinization have the same state complexity, namely (2 n ) where n is the state size. The same similarity between determinization and complementation