Nondeterministic finite state complexity

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$).

G S0111V0 S0111V0 S0111V1 S0111V1 S0111V0->S0111V1 0 S0111V1->S0111V1 1 S0101V0 S0101V0 S0101V1 S0101V1 S0101V0->S0101V1 0 S0101V1->S0101V0 1 S0001V0 S0001V0 S0001V0->S0001V0 0 S0001V1 S0001V1 S0001V0->S0001V1 1 S0000V0 S0000V0 S0000V0->S0000V0 0