Graduate student Kayleigh Hyde will present her Master’s project on Monday April 22, 10:30am, in Shidler College of Business Room E201. Draft paper

Let $M$ be a nondeterministic finite automaton, having $q$ states and no $\epsilon$-transitions. If there is exactly one path through $M$ of length $n$ leading to an accept state, and $x$ is the string read along that path, then we say that $A_N(x)\le q$ (the NFS complexity of $x$ is at most $q$).