Re: Average-case analysis of Hopcroft's DFA minimization algorithm?
- From: "NUPUL" <nupul.kukreja@xxxxxxxxx>
- Date: 15 Feb 2007 01:46:59 -0800
On Feb 11, 5:07 am, Sheldon Nicholl <sheld...@xxxxxxxxxxx> wrote:
Has anyone done an average-case analysis of the running time of
Hopcroft's n log n DFA minimization algorithm? I can find no
average case analyses, even in modern reports such as [1] or [2].
If not, has anyone done other kinds of average-case analyses
of other interesting algorithms on deterministic finite-state
automata, to give an idea of how this is done?
I suggest you look at the classic text book of Hopcroft, Ullman and
Motwani on Automata theory and languages. There the DFA Minimization
algorithm has been analysed in good detail w.r.t the table filling
algorithm (which is NOT O(nlogn)).
Took look for the average case "explanation" go through the "dragon
book" of compilers - Compilers: Principles and techniques - Aho, Sethi
and Ullman. They have given a good explanation of the algorithm - in a
manner that the average/worst/best cases can easily be "worked out"
I hope they are useful.
Nupul.
.
- References:
- Average-case analysis of Hopcroft's DFA minimization algorithm?
- From: Sheldon Nicholl
- Average-case analysis of Hopcroft's DFA minimization algorithm?
- Prev by Date: Re: Hofman and Diaby talk about P=NP at INFORMS 2007
- Next by Date: Re: Hofman and Diaby talk about P=NP at INFORMS 2007
- Previous by thread: Average-case analysis of Hopcroft's DFA minimization algorithm?
- Next by thread: Errors in Papademetriou?
- Index(es):
Relevant Pages
|
