Re: DFA minimalization

mareg_at_mimosa.csv.warwick.ac.uk
Date: 01/15/04 

Date: Thu, 15 Jan 2004 12:38:50 +0000 (UTC)

In article <bu5ua5$6g0$1@panorama.wcss.wroc.pl>,
        "Piotr Wyderski" <NotAHelpdeskSend@ll.replies.to.the.group> writes:
>Hello,
>
>what is the most efficient DFA minimalization algorithm?
>There is an example in the book of Hopcroft and Ullman,
>but even they claim themselves that it isn't the fastest
>known way. So what is the best AD 2004? :-) Links
>to detailed papers or at least some phrases to feed google
>would be appreciated.
>
> Best regards
> Piotr Wyderski

I don't know the answer to this, but I am very interested in the problem,
since I regularly need to minimize very large DFA's in the course of some
computations in group theory.

Currently I use a simple-minded O(n^2) algorithm, because it is very
efficient in terms of memory usage. Indeed, the input DFA does not even need
to be stored in RAM, because the algorithm works by repeatedly reading
through the transition table sequentially. So the RAM usage is about the
same as for storing the minimized DFA.

I have for some time been trying to find out whether there are implementations
of an O(n log n) minimization algorithm for which the memory requirement does
not greatly exceed the storage required for the input DFA - I would regard
twice that amount as unacceptable.

Derek Holt.

Relevant Pages

  • RE->DFA with subexpression matching
    ... Given a set of regular expressions, create a DFA that would recognize ... an algorithm that, I think, could solve the problem. ... It's based on tagged automata and I've described it here: ... Any comment and suggestion will be welcome! ...
    (comp.compilers)
  • Re: Slow ruby regexes
    ... > This would be true if the Thompson algorithm was caching the states as ... There is a section in his article entitled "Caching the NFA to build a DFA" with code doing exactly that. ...
    (comp.lang.ruby)
  • Re: corrections on a dfas input strings?
    ... removing keys from it, or even perfoming completion as readline does ... corrrections on input strings against those already registered within ... the dfa. ... I'm surprised no one has mentioned the soundex algorithm, ...
    (comp.compilers)
  • Re: Testing for acceptance of Kleene closure of alphabet
    ... An alternative is leaning on the algorithm for minimizing a DFA ... and the fact that any regular language has a unique minimal DFA. ...
    (comp.theory)
  • Re: DFA minimalization
    ... Piotr Wyderski wrote: ... >what is the most efficient DFA minimalization algorithm? ... Experiments suggest that in practice Brzozowski's algorithm is most ...
    (comp.theory)