The method of forced enumeration for nondeterministic automata. (English) Zbl 0638.68046

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.
Reviewer: R.Szelepcsényí


68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Reading: Addison-Wesley 1969 · Zbl 0196.01701
[2] Immerman, N.: Nondeterministic space is closed under complementation. Proceedings of the 3rd Annual Conference Structure in Complexity Theory, 14-17 June 1988, Washington D.C. (also TH Report YALEU/DCS/TR 552, July 1987)
[3] Immerman, N.: Descriptive and computational complexity, (unpublished manuscript, 1987) · Zbl 0634.68034
[4] Kuroda, S.Y.: Classes of languages and linear-bounded automata. Inf. Control 7, 207-233 (1964) · Zbl 0199.04002 · doi:10.1016/S0019-9958(64)90120-2
[5] Szelepcsényi, R.: Context-sensitive languages are closed under complementation, TR Komensky University, April 1987 (in Slovak)
[6] Szelepcsényi, R.: The method of Forcing for nondeterministic automata. Bull. Eur. Assoc. Theor. Comp. Sci. 33, 96-100 (1987) · Zbl 0664.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.