notice
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.