n South African Computer Journal - Minimization of unary symmetric difference NFAs : reviewed article
|Article Title||Minimization of unary symmetric difference NFAs : reviewed article|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Author||Lynette Van Zijl, Graham Muller and Jan Daciuk|
|Publication Date||Jun 2005|
|Pages||69 - 75|
|Keyword(s)||Automata theory, Descriptional omplexity, Nondeterminism and Succinctness|
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.
Article metrics loading...