About the MERLin Project
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.
Super-NFAs
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.
Some of our past, current and proposed projects
- Generalized Nondeterminism in Tree Automata
- Applications of Generalized Nondeterminism
- Venn Planarity and Venn Diagram Layout
- Selective Nondeterminism in Shift Register Sequences
- Generalized Nondeterminism in Automata on Infinite Words
- Circuit Synthesis using Generalized Automata
- Coding Theory using Generalized Automata