FsmRegForm  

AbbrName  MERLin 
FullName  MERLin 
ItemDesc 
In the MERLin project, we are concerned with generalizations of nondeterminism, and in particular generalizations that will lead to succinct descriptions of regular languages. One example of generalized nondeterminism is selective nondeterminism. Here, the subset construction is generalized to allow any binary commutative set operation to be used in the subset construction, instead of only union, as is the case with traditional NFAs. Some interesting results on selective nondeterminism include: * There is a close correspondence between linear feedback shift registers and unary symmetrical difference NFAs. * A standard nstate (union) NFA seldom yields a minimal DFA with 2^n states, while the symmetric difference NFA often does (this result relates to maximal sequences in FSRs, which correspond to primitive polynomials in GF(2)). * It is possible to construct nstate intersection NFAs such that the shortest word accepted by the NFA has length strictly greater than n. SuperNFAs Other generalizations of nondeterminism include the socalled superNFAs, which allow the transition function of the NFA to be a mapping from Q to P(P..(P(Q))..) where P is the powerset operator, applied k times. Here we showed that a superNFA with k=2 is equivalent to a boolean (alternating) automaton. With a generalization of acceptance, we also constructed a 2state superNFA with k=3 such that its minimal equivalent DFA has 17 states (that is, strictly more than 2^(2^2)). Related issues Certain interesting sideissues arise from the study of generalized nondeterminism. For example, drawing a standard NFA as a state graph has an intuitive interpretation; the same cannot be said for other selectively NFAs. We are currently investigating suitable visual representations for *NFAs, with the most promising candidate at the moment being Venn diagrams. In addition, we are looking at drawing algorithms for Venn diagrams on congruent forms.

APartOf 

ContainsParts 

HomePage  http://www.cs.sun.ac.za/~lynette/MERLin/ 
Type  FsmCompiler 
ImplLanguage 

Author 

Copyright 

License 

References 

Availability 

ProviderName 

RelatedWork 

Evaluation 

LatestVersion 

TWiki Reference