Minimization of unary symmetric difference NFAs : reviewed article
Lynette van Zijl, Graham Müller, Jan Daciuk · South African Computer Journal · 2005
We investigate the minimization of unary symmetric difference nondeterministic finite automata. To this end, we develop a modification of the Berlekamp-Massey algorithm. We then prove that, given a unary symmetric difference nondeterministic finite automaton with one final state, this modified algorithm produces a minimal symmetric difference nondeterministic finite automaton which accepts the same language. We also discuss the application of the technique in the case where the nondeterministic finite automaton has more than one final state. Finally, we consider compression, as opposed to minimization, of symmetric difference nondeterministic finite automata.