On the Hopcroft's minimization algorithm

Details On the Hopcroft's minimization algorithm On the Hopcroft's minimization algorithm

2007-05-14

arxiv.org/abs/0705.1986v1

Computer Science

Data Structures and Algorithms

10 pages, 1 figure

Scientific paper

We show that the absolute worst case time complexity for Hopcroft's minimization algorithm applied to unary languages is reached only for de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires O(n log n) steps by carefully choosing the splitting sets and processing these sets in a FIFO mode. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages. We also show that a LIFO implementation will not achieve the same worst time complexity for the case of unary languages. Lastly, we show that the same result is valid also for the cover automata and a modification of the Hopcroft's algorithm, modification used in minimization of cover automata.

Affiliated with

Also associated with

No associations

Rating

On the Hopcroft's minimization algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Hopcroft's minimization algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Hopcroft's minimization algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-366116