Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!utcsri!arvind
From: arvind@utcsri.UUCP
Newsgroups: ut.theory
Subject: THEORY NET: NSPACE
Message-ID: <5657@utcsri.UUCP>
Date: Fri, 13-Nov-87 11:58:07 EST
Article-I.D.: utcsri.5657
Posted: Fri Nov 13 11:58:07 1987
Date-Received: Sun, 15-Nov-87 03:51:32 EST
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 18

Date:         10 Nov 1987 18:08:04-EST (Tuesday)
From: Paul Vitanyi <MCVAX!CWI.NL!PAULV@uunet.uu.net>
Subject:      NSPACE

In the EATCS Bulletin of October 1987 (Number 33), pp. 94-100,
there is an article by Robert Szelepcsenyi ``The method
of forcing for nondeterministic automata'', claiming
the result
     
NSPACE (L(n)) is closed under complement for L(n) >= log n
     
The author refers to an earlier tech rept (in Slovak):
     
``R. Szelepcsenyi, Context-sensitive languages are closed
under complementation, Tech. rept. Komensky University,
April 87.
     
The author does not refer Neil Immerman.