DFA Minimization Algorithms in Map-Reduce and the Complexity

Map-Reduce has been a highly popular parallel-distributed programming model. In this book, we study the problem of minimizing Deterministic Finite State Automata (DFA). We focus our attention on two well-known (serial) algorithms, namely the algorithms of Moore (1956) and of Hopcroft (1971). The central cost parameter in Map-Reduce is that of Communication Cost. Using techniques from Communication Complexity we derive a lower bound and upper bound for the problem. We then develop Map-Reduce versions of both Moore's and Hopcroft's algorithms and show that their communication cost is the same. Both methods have been implemented and tested on large DFA, with 131,072 states. The experiments verify our theoretical analysis, and also reveal that Hopcroft's algorithm -- considered superior in the sequential framework -- is very sensitive to skew in the topology of the graph of the DFA, whereas Moore's algorithm handles skew without major efficiency loss.