Re: Compress the finite state machine

Torben Mogensen <torbenm@diku.dk>
22 Mar 1999 01:13:02 -0500

          From comp.compilers

Related articles
Compress the finite state machine felixmish@usa.net (Felix Mish) (1999-03-02)
Re: Compress the finite state machine cfc@world.std.com (Chris F Clark) (1999-03-04)
Re: Compress the finite state machine torbenm@diku.dk (Torben Mogensen) (1999-03-04)
Re: Compress the finite state machine jes6@eecs.lehigh.edu (James E. Stine) (1999-03-04)
Re: Compress the finite state machine allanmac@blueprint.com (Allan MacKinnon) (1999-03-04)
Re: Compress the finite state machine hunk@alpha1.csd.uwm.edu (1999-03-04)
Re: Compress the finite state machine stans@lucent.com (Sicco Tans) (1999-03-10)
Re: Compress the finite state machine torbenm@diku.dk (Torben Mogensen) (1999-03-22)
Re: Compress the finite state machine sassth@unx.sas.com (Steven Hand) (1999-03-22)
| List of all articles for this month |

From: Torben Mogensen <torbenm@diku.dk>
Newsgroups: comp.compilers
Date: 22 Mar 1999 01:13:02 -0500
Organization: Compilers Central
References: 99-03-010 99-03-017
Keywords: DFA

>> The first step is, obviously, to minimize the number of states in the
>> DFA. You can find a method for this in Aho, Sethi and Ullman's
>> compiler book, though the version described there isn't particularly
>> efficient.


>Does anyone have a more efficient way to minimize the number of
>states in the DFA?


The method described in the abovementioned book uses in the worst case
quadratic time (even though it is elsewhere in the book claimed to be
O(n*log(n))). An O(n*log(n)) method can be found in Aho, Hopcroft and
Ullman's "The Design and Analysis of Computer Algorithms".


An improved version was published by Keller and Paige in
Communications of Pure and Applied Math., Vol 48, Num. 9-10, 1996. It
can also be found at http://cs.nyu.edu/cs/faculty/paige/research.html
(search for "minimum-state" within this page).


Torben Mogensen (torbenm@diku.dk)


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.