1887

n South African Computer Journal - Minimization of unary symmetric difference NFAs : reviewed article

USD

 

Abstract

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.

Loading

Article metrics loading...

/content/comp/2005/34/EJC27980
2005-06-01
2016-12-04
This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error