MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS
Abstract
Iwama et al. showed that there exists an n-state binary nondeterministic finite automaton such that its equivalent minimal deterministic finite automaton has exactly 2n - α states, for all n ≥ 7 and 5 ≤ α ≤ 2n-2, subject to certain coprimality conditions. We investigate the same question for both unary and binary symmetric difference nondeterministic finite automata. In the binary case, we show that for any n ≥ 4, there is an n-state symmetric difference nondeterministic finite automaton for which the equivalent minimal deterministic finite automaton has 2n - 1 + 2k - 1 - 1 states, for 2 < k ≤ n - 1. In the unary case, we consider a large practical subclass of unary symmetric difference nondeterministic finite automata: for all n ≥ 2, we argue that there are many values of α such that there is no n-state unary symmetric difference nondeterministic finite automaton with an equivalent minimal deterministic finite automaton with 2n - α states, where 0 < α < 2n - 1. For each n ≥ 2, we quantify such values of α precisely.
