389:, and must find an equivalent automaton with as few states as possible. Hopcroft's algorithm maintains a partition of the states of the input automaton into subsets, with the property that any two states in different subsets must be mapped to different states of the output automaton. Initially, there are two subsets, one containing all the accepting states of the automaton and one containing the remaining states. At each step one of the subsets
204:
that allows for rapid deletion of individual elements from the collection. Alternatively, this component of the data structure may be represented by storing all of the elements of all of the sets in a single array, sorted by the identity of the set they belong to, and by representing the collection
369:, independent of the number of elements in the family of sets and also independent of the total number of sets in the data structure. Thus, the time for a sequence of refinements is proportional to the total size of the sets given to the algorithm in each refinement step.
497:
used to refine the partition are sets of neighbors of vertices. Since the total number of neighbors of all vertices is just the number of edges in the graph, the algorithm takes time linear in the number of edges, its input size.
612:
Habib, Michel; Paul, Christophe; Viennot, Laurent (1998), "A synthesis on partition refinement: a useful routine for strings, graphs, Boolean matrices and automata", in Morvan, Michel; Meinel, Christoph; Krob, Daniel (eds.),
492:
in linear time; this lexicographic topological ordering is one of the key steps of the
Coffman–Graham algorithm. In this application, the elements of the disjoint sets are vertices of the input graph and the sets
428:
that has already been chosen is split by a refinement, only one of the two resulting sets (the smaller of the two) needs to be chosen again; in this way, each state participates in the sets
577:
673:, Leibniz International Proceedings in Informatics (LIPIcs), vol. 1, Dagstuhl, Germany: Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, pp. 645–656,
86:. At the start of the algorithm, this family contains a single set of all the elements in the data structure. At each step of the algorithm, a set
871:
Graph-Theoretic
Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers
32:
that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the
355:
from the second set that has been split from it, and reports both of these sets as being newly formed by the refinement operation.
575:
Habib, Michel; Paul, Christophe; Viennot, Laurent (1999), "Partition refinement techniques: an interesting algorithmic tool kit",
723:
890:
698:
639:
869:(2004), "Lexicographic breadth first search – a survey", in Hromkovič, Juraj; Nagl, Manfred; Westfechtel, Bernhard (eds.),
616:
STACS 98: 15th Annual
Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998, Proceedings
502:
64:
41:
874:
623:
276:
of the sets that are split by the operation. Then, regardless of whether a new set was formed, the algorithm removes
182:
663:
Valmari, Antti; Lehtinen, Petri (2008), "Efficient minimization of DFAs with partial transition functions", in
386:
402:
of the automaton are chosen, and the subsets of states are refined into states for which a transition labeled
478:
60:
514:
509:
and several other important classes of graphs. Again, the disjoint set elements are vertices and the set
33:
40:
but in which the operations merge pairs of sets. In some applications of partition refinement, such as
839:
798:
540:
106:
912:
124:
489:
223:
To perform a refinement operation, the algorithm loops through the elements of the given set
819:
779:
708:
649:
598:
561:
201:
8:
482:
674:
614:
197:
164:
25:
736:
886:
740:
694:
635:
772:
Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971)
670:
25th
International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
668:
878:
848:
807:
732:
689:
684:
627:
586:
549:
485:
382:
306:. In the representation in which all elements are stored in a single array, moving
56:
52:
815:
775:
704:
645:
594:
557:
44:, the data structure maintains as well an ordering on the sets in the partition.
882:
837:; Lueker, G. S. (1976), "Algorithmic aspects of vertex elimination on graphs",
664:
145:
29:
590:
47:
Partition refinement forms a key component of several efficient algorithms on
906:
866:
834:
757:
744:
535:
506:
481:
for parallel scheduling. Sethi showed that it could be used to construct a
48:
37:
793:
631:
261:
has already been started. If not, it creates the second set and adds
75:
A partition refinement algorithm maintains a family of disjoint sets
17:
852:
811:
553:
377:
An early application of partition refinement was in an algorithm by
505:, a graph search algorithm with applications in the recognition of
336:
and the start index of the new set. Finally, after all elements of
167:
that allows new sets to be inserted into the middle of the sequence
679:
721:
Knuutila, Timo (2001), "Re-describing an algorithm by
Hopcroft",
358:
The time to perform a single refinement operation in this way is
144:
Such an algorithm may be implemented efficiently by maintaining
340:
have been processed in this way, the algorithm loops through
770:
algorithm for minimizing states in a finite automaton",
578:
International
Journal of Foundations of Computer Science
447:
refinement steps and the overall algorithm takes time
310:
from one set to another may be performed by swapping
219:
Associated with each element, the set it belongs to.
626:, vol. 1373, Springer-Verlag, pp. 25–38,
216:
by its starting and ending positions in this array.
877:, vol. 3353, Springer-Verlag, pp. 1–19,
419:-transition would lead somewhere else. When a set
538:(1987), "Three partition refinement algorithms",
904:
832:
611:
574:
796:(1976), "Scheduling graphs on two processors",
662:
774:, New York: Academic Press, pp. 189–196,
501:Partition refinement also forms a key step in
90:is presented to the algorithm, and each set
533:
385:. In this problem, one is given as input a
688:
678:
756:
720:
378:
148:representing the following information:
36:, which also maintains a partition into
865:
325:and then decrementing the end index of
101:in the family that contains members of
905:
517:, so the algorithm takes linear time.
477:in an efficient implementation of the
246:, and checks whether a second set for
792:
474:
473:Partition refinement was applied by
466:is the number of initial states and
163:in the family, in a form such as a
13:
503:lexicographic breadth-first search
65:lexicographic breadth-first search
42:lexicographic breadth-first search
24:is a technique for representing a
14:
924:
875:Lecture Notes in Computer Science
624:Lecture Notes in Computer Science
152:The ordered sequence of the sets
70:
372:
859:
826:
786:
750:
714:
690:10.4230/LIPIcs.STACS.2008.1328
656:
605:
568:
527:
387:deterministic finite automaton
344:, separating each current set
1:
737:10.1016/S0304-3975(99)00150-4
520:
470:is the size of the alphabet.
398:and one of the input symbols
63:for parallel scheduling, and
724:Theoretical Computer Science
105:is split into two sets, the
7:
883:10.1007/978-3-540-30559-0_1
10:
929:
415:, and states for which an
314:with the final element of
840:SIAM Journal on Computing
799:SIAM Journal on Computing
591:10.1142/S0129054199000125
541:SIAM Journal on Computing
483:lexicographically ordered
170:Associated with each set
34:union-find data structure
479:Coffman–Graham algorithm
227:. For each such element
61:Coffman–Graham algorithm
667:; Weil, Pascal (eds.),
205:of elements in any set
490:directed acyclic graph
196:, in a form such as a
202:array data structure
22:partition refinement
231:, it finds the set
185:of its elements of
632:10.1007/BFb0028546
198:doubly linked list
165:doubly linked list
26:partition of a set
892:978-3-540-24132-4
867:Corneil, Derek G.
700:978-3-939897-06-4
641:978-3-540-64230-5
536:Tarjan, Robert E.
515:sets of neighbors
16:In the design of
920:
897:
895:
863:
857:
855:
830:
824:
822:
790:
784:
782:
769:
754:
748:
747:
731:(1–2): 333–363,
718:
712:
711:
692:
682:
660:
654:
652:
621:
609:
603:
601:
572:
566:
564:
531:
512:
496:
486:topological sort
469:
465:
461:
446:
431:
427:
418:
414:
405:
401:
397:
383:DFA minimization
368:
354:
343:
339:
335:
324:
313:
309:
305:
290:
279:
275:
271:
260:
245:
241:
230:
226:
215:
195:
180:
162:
140:
122:
104:
100:
89:
85:
57:DFA minimization
928:
927:
923:
922:
921:
919:
918:
917:
913:Data structures
903:
902:
901:
900:
893:
864:
860:
853:10.1137/0205021
831:
827:
812:10.1137/0205005
791:
787:
761:
755:
751:
719:
715:
701:
665:Albers, Susanne
661:
657:
642:
619:
610:
606:
573:
569:
554:10.1137/0216062
534:Paige, Robert;
532:
528:
523:
510:
494:
467:
463:
448:
433:
429:
425:
420:
416:
412:
407:
403:
399:
395:
390:
379:Hopcroft (1971)
375:
359:
353:
345:
341:
337:
334:
326:
323:
315:
311:
307:
300:
292:
291:and adds it to
289:
281:
277:
273:
270:
262:
255:
247:
243:
240:
232:
228:
224:
214:
206:
194:
186:
179:
171:
161:
153:
146:data structures
135:
127:
117:
109:
102:
99:
91:
87:
84:
76:
73:
53:finite automata
12:
11:
5:
926:
916:
915:
899:
898:
891:
858:
847:(2): 266–283,
825:
785:
758:Hopcroft, John
749:
713:
699:
655:
640:
604:
585:(2): 147–170,
567:
548:(6): 973–989,
525:
524:
522:
519:
507:chordal graphs
423:
410:
406:would lead to
393:
374:
371:
349:
330:
319:
296:
285:
266:
251:
242:that contains
236:
221:
220:
217:
210:
190:
175:
168:
157:
131:
113:
95:
80:
72:
71:Data structure
69:
30:data structure
9:
6:
4:
3:
2:
925:
914:
911:
910:
908:
894:
888:
884:
880:
876:
872:
868:
862:
854:
850:
846:
842:
841:
836:
835:Tarjan, R. E.
833:Rose, D. J.;
829:
821:
817:
813:
809:
805:
801:
800:
795:
789:
781:
777:
773:
768:
764:
759:
753:
746:
742:
738:
734:
730:
726:
725:
717:
710:
706:
702:
696:
691:
686:
681:
676:
672:
671:
666:
659:
651:
647:
643:
637:
633:
629:
625:
618:
617:
608:
600:
596:
592:
588:
584:
580:
579:
571:
563:
559:
555:
551:
547:
543:
542:
537:
530:
526:
518:
516:
508:
504:
499:
491:
487:
484:
480:
476:
471:
459:
455:
451:
444:
440:
436:
426:
413:
396:
388:
384:
380:
370:
366:
362:
356:
352:
348:
333:
329:
322:
318:
304:
299:
295:
288:
284:
269:
265:
259:
254:
250:
239:
235:
218:
213:
209:
203:
199:
193:
189:
184:
178:
174:
169:
166:
160:
156:
151:
150:
149:
147:
142:
139:
134:
130:
126:
121:
116:
112:
108:
98:
94:
83:
79:
68:
66:
62:
58:
54:
50:
45:
43:
39:
38:disjoint sets
35:
31:
27:
23:
19:
870:
861:
844:
838:
828:
806:(1): 73–82,
803:
797:
788:
771:
766:
762:
760:(1971), "An
752:
728:
722:
716:
669:
658:
615:
607:
582:
576:
570:
545:
539:
529:
500:
475:Sethi (1976)
472:
457:
453:
449:
442:
438:
434:
421:
408:
391:
376:
373:Applications
364:
360:
357:
350:
346:
331:
327:
320:
316:
302:
297:
293:
286:
282:
267:
263:
257:
252:
248:
237:
233:
222:
211:
207:
191:
187:
176:
172:
158:
154:
143:
137:
132:
128:
119:
114:
110:
107:intersection
96:
92:
81:
77:
74:
55:, including
46:
21:
15:
794:Sethi, Ravi
513:represents
488:of a given
67:of graphs.
521:References
272:to a list
183:collection
125:difference
18:algorithms
745:0304-3975
680:0802.2826
907:Category
462:, where
301:∩
256:∩
123:and the
118:∩
820:0398156
780:0403320
709:2873773
650:1650757
599:1759929
562:0917035
367:|)
363:(|
889:
818:
778:
743:
707:
697:
648:
638:
597:
560:
59:, the
49:graphs
675:arXiv
620:(PDF)
280:from
28:as a
887:ISBN
765:log
741:ISSN
695:ISBN
636:ISBN
456:log
441:log
432:for
381:for
181:, a
51:and
879:doi
849:doi
808:doi
733:doi
729:250
685:doi
628:doi
587:doi
550:doi
200:or
909::
885:,
873:,
843:,
816:MR
814:,
802:,
776:MR
739:,
727:,
705:MR
703:,
693:,
683:,
646:MR
644:,
634:,
622:,
595:MR
593:,
583:10
581:,
558:MR
556:,
546:16
544:,
454:ns
141:.
136:\
20:,
896:.
881::
856:.
851::
845:5
823:.
810::
804:5
783:.
767:n
763:n
735::
687::
677::
653:.
630::
602:.
589::
565:.
552::
511:X
495:X
468:s
464:n
460:)
458:n
452:(
450:O
445:)
443:n
439:s
437:(
435:O
430:X
424:i
422:S
417:x
411:i
409:S
404:x
400:x
394:i
392:S
365:X
361:O
351:i
347:S
342:L
338:X
332:i
328:S
321:i
317:S
312:x
308:x
303:X
298:i
294:S
287:i
283:S
278:x
274:L
268:i
264:S
258:X
253:i
249:S
244:x
238:i
234:S
229:x
225:X
212:i
208:S
192:i
188:S
177:i
173:S
159:i
155:S
138:X
133:i
129:S
120:X
115:i
111:S
103:X
97:i
93:S
88:X
82:i
78:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.