22 Mar 1999 01:13:02 -0500

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) |

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.