Degree
Master of Science
Program
Computer Science
Supervisor
Dr. Roberto Solis-Oba
Abstract
In this thesis, we study in minimum vertex cover problem on the class of k-partite k-uniform hypergraphs. This problem arises when reducing the size of nondeterministic finite automata (NFA) using preorders, as suggested by Champarnaud and Coulon. It has been shown that reducing NFAs using preorders is at least as hard as computing a minimal vertex cover on 3-partite 3-uniform hypergraphs, which is NP-hard. We present several classes of regular languages for which NFAs that recognize them can be optimally reduced via preorders. We introduce an algorithm for approximating vertex cover on k-partite k-uniform hypergraphs based on a theorem by Lovász and explore the use of fractional cover algorithms to improve the running time at the expense of a small increase in the approximation ratio.
Recommended Citation
Ng, Timothy, "NFA reduction via hypergraph vertex cover approximation" (2013). Electronic Thesis and Dissertation Repository. 1224.
https://ir.lib.uwo.ca/etd/1224