Hi, thanks for taking the time to consider my problem. On Mon, Aug 05, 2002 at 07:12:12PM -0700, oleg@pobox.com wrote:
To prevent such a behavior we ought to keep track of the states that we have already computed.
Yes, this is definitely an approach. Perhaps it is the best one after all, but I was interested in exploring the use of a recursive datatype: I wonder how much faster and efficient it can make the implementation (by avoiding linear searches through a state-label association list.) I also wonder whether this approach is so much different than the one I described, once composed with finAuConsolidate. I guess this is really part of my question. If so, then I prefer the finAuConsolidate approach, since it extracts and generalizes the problem so that other inductive algorithms may be coded up intuitively, then merely composed with finAuConsolidate. A large part of what I'm looking for at the moment is simply to find a fast and efficient way to express cyclic graphs in Haskell because in a present research project I need to manipulate machines with hundreds and thousands of states and my current, simple implementation simply won't do: my jobs balloon in size and die. At the same time, code written and run in the early eighties outperforms mine!! (Blushing with shame.) Basically, I'm trying to find out whether Haskell is inherently that much slower or whether I am simply not yet quite competent enough to approach the problem correctly.
(BTW, I had trouble with the automaton in the original article. That NFA recognized [1], which it should not). The acceptance function can be written as
I'm sorry, the automaton was right, the regexp wrong (in the sense that it's a very important language in my work); it should be (0(0+1))* + ((0+1)0)* I was just trying to simplify this and made a mistake, I suppose I was aiming at 0*((0+1)0)*. Thanks, Carl