The method of forcing for nondeterministic automata. (English) Zbl 0664.68082

The problem if context-sensitive languages are closed under complementation has been open since 1964. The affirmative response for this problem was given independently in 1987 by two authors: N. Immerman [Nondeterministic space is closed under complement, Yale Univ. Tech. Rep., August 1987 (cf. SIAM J. Comput. 17, No.5, 935-938 (1988))] and the author [Context-sensitive languages are closed under complementation, Comenius Univ. Tech. Rep., April, 1987]. The paper under review contains an informal presentation of the method used by the last author.
Reviewer: D.Lucanu


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