Map-Reduce has been a highly popular parallel-distributed programming model. In this thesis, 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 i.e., the amount of data that has to be communicated between the processes. Using techniques from Communication Complexity we derive an O(kn log{n}) lower bound and O(kn^3 log{n}) upper bound for the problem, where n is the number of states in the DFA to be minimized,and k is the size of its alphabet. We then develop Map-Reduce versions of both Moore's and Hopcroft's algorithms, and show that their communication cost is O(kn^2 (log {n} + log {k})). 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.