State minimization problems in finite state automata [electronic resource] /
State Minimization Problems in Finite State Automata
Master of Science in Computer Science
West Virginia University
K. Subramani, Ph.D., Chair
In this thesis, we analyze the problem of state minimization in 2-MDFAs. The class of
2-MDFAs is an extension of the class of DFAs, allowing a small amount of nondeterminism;
specifically two start states. Since nondeterminism allows finite automata to be more succinct,
it is worthwhile to investigate the problem of minimizing such finite automata. In the case of
unbounded non- determinism, i.e., NFAs, such automata can be exponentially more succinct
than DFAs , but the corresponding minimization problem is PSPACE-complete 
. Even in
the case of 2-MDFAs, which are only polynomially more succinct than DFAs, the minimization
problem remains non-trivial; indeed,  shows that the corresponding decision problem is NPcomplete.
We are concerned with the approximability of the 2-MDFA minimization problem.
Our main contribution in the current work is the design of an n-factor approximation algorithm
for state minimization in 2-MDFAs.
School:West Virginia University
School Location:USA - West Virginia
Source Type:Master's Thesis
Keywords:sequential machine theory
Date of Publication: