Back to: FsmReg
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 n-state (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 n-state intersection NFAs such that the shortest word accepted by the NFA has length strictly greater than n.

Other generalizations of nondeterminism include the so-called super-NFAs, 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 super-NFA with k=2 is equivalent to a boolean (alternating) automaton. With a generalization of acceptance, we also constructed a 2-state super-NFA with k=3 such that its minimal equivalent DFA has 17 states (that is, strictly more than 2^(2^2)).

Related issues
Certain interesting side-issues 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.



Type FsmCompiler










Topic revision: r1 - 2008-10-24 - AnssiYliJyra
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback