Titlebook: Automata, Languages and Programming; 33rd International C Michele Bugliesi,Bart Preneel,Ingo Wegener Conference proceedings 2006 Springer-V

Spina-Bifida

Small Sweeping 2NFAs Are Not Closed Under ComplementA two-way nondeterministic finite automaton is . (.) if its input head can change direction only on the end-markers. For every ., we exhibit a language that can be recognized by an .-state . but requires . states on every . recognizing its complement.