The method of forced enumeration for nondeterministic automata (Q1099620): Difference between revisions

The paper presents a new method of simulating nondeterministic Turing machines. The method forces every accepting computation of a nondeterministic Turing machine to examine all reachable configurations of the simulated nondeterministic Turing machine working on an input word w. It is important that the simulating machine does not use more space than the original Turing machine. Using the new method we prove that every family of languages, recognized by nondeterministic L(n) tape-bounded Turing machines for L(n)\(\geq \log n\) is closed under complement. As a special case the closure of context- sensitive languages under complement follows.