The Prague Stringology Conference 2002
Jean-Marc Champarnaud, A. Khorsi and T. Paranthoën
Split and join for minimizing: Brzozowski's algorithm
| Abstract: |
| Brzozowski's minimization algorithm is based on two successive determinization operations. There is a paradox between its (worst case) exponential complexity and its exceptionally good performance in practice. Our aim is to analyze the way the twofold determinization performs the minimization of a deterministic automaton. We give a characterization of the equivalence classes of A w.r.t. the set of states of the automaton computed by the first determinization. The second determinization is expected to compute these equivalence classes. We show that it can be replaced by a specific procedure based on the classes characterization, which leads to a more efficient variant of Brzozowski's algorithm. |
| Download paper: |  |
 |
| PostScript |