Spina-Bifida
发表于 2025-4-1 04:27:47
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.