Login | Register

Finite Automata Algorithms in Map-Reduce


Finite Automata Algorithms in Map-Reduce

Harrafi Saveh, Shahab (2015) Finite Automata Algorithms in Map-Reduce. Masters thesis, Concordia University.

[thumbnail of Harrafi_MCompSc_S2015.pdf]
Text (application/pdf)
Harrafi_MCompSc_S2015.pdf - Accepted Version
Available under License Spectrum Terms of Access.


In this thesis the intersection of several large nondeterministic finite automata (NFA's) as well as minimization of a large deterministic finite automaton (DFA) in map-reduce are studied. We have derived a lower bound on replication rate for computing NFA intersections and provided three concrete algorithms for the problem. Our investigation of the replication rate for each of all three algorithms shows where each algorithm could be applied through detailed experiments on large datasets of finite automata. Denoting n the number of states in DFA A, we propose an algorithm to minimize A in n map-reduce rounds in the worst-case. Our experiments, however, indicate 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.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Harrafi Saveh, Shahab
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:15 April 2015
Thesis Supervisor(s):Grahne, Gösta
Keywords:Map-Reduce, Hadoop, Automata, NFA Intersections, DFA Minimization
ID Code:979999
Deposited On:13 Jul 2015 15:52
Last Modified:18 Jan 2018 17:50
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top