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: Article in PostScript Article in PDF
 PostScript   PDF