Master Thesis Defense: Shahab Harrafi Saveh

Speaker: Shahab Harrafi Saveh

Supervisor: Dr. G. Grahne

Examining Committee: Drs. L. Narayanan, N. Shiri, E. J. Doedel (Chair)

Title: Finite Automata Algorithms in Map-Reduce

Date: Wednesday, April 15, 2014

Time: 10:00 a.m.

Place: EV 11.119

ABSTRACT

In this thesis intersection of several huge nondeterministic finite automata (NFA's) as well as minimization of a large deterministic finite automaton (DFA) in map-reduce are studied. We have derived the lower bound on replication rate for computing NFA intersections and provided three concrete algorithms for the problem. Our investigation of the upper bound on replication rate for each of all three algorithms shows where each algorithm could be applied through detailed experiments on large datasets. Denoting n the number of states in DFA A, we proposed an algorithm to minimize A in n map-reduce rounds in the worst-case. Our experiments, however, indicates that the number of rounds, in practice, is much smaller than n for all DFA's we examined. In other words, this algorithm converges in d iterations by computing the equivalence classes of each state, where d is the diameter of the input DFA.