Intersection non-emptiness for restricted classes of Deterministic Finite Automata

Abstract

In this thesis, the intersection non-emptiness problem for Deterministic Finite Automata is discussed. By applying certain restrictions to the Deterministic Finite Automata, an algorithm is constructed to analyze whether the given restricted Automata share any common strings. The time complexity of this algorithm is then discussed and compared to previous research on this subject.