chang@svax.cs.cornell.edu (Richard Chang) (11/22/90)
Questions about references:
Does anyone know a journal version for these papers?
1. Szelepcsenyi's version of NSPACE[f(n)] = co-NSPACE[f(n)]
(It was called "On the method of forcing for nondeterministic
automata" in the Bulletin of the EATCS. Is there a
conference version??)
2. The Karp-Lipton paper "Some connections between nonuniform
and uniform complexity classes." I only have a reference
to the STOC '80 version.
Thanks
Richardchang@svax.cs.cornell.edu (Richard Chang) (11/27/90)
In article <48718@cornell.UUCP> chang@cs.cornell.edu (Richard Chang) writes: >Questions about references: > >Does anyone know a journal version for these papers? > >1. Szelepcsenyi's version of NSPACE[f(n)] = co-NSPACE[f(n)] > (It was called "On the method of forcing for nondeterministic > automata" in the Bulletin of the EATCS. Is there a > conference version??) Apparently, no conference version is available. The paper was published under the new title: "The Method of Forced Enumeration for Nondeterministic Automata", Acta Informatica, volume 26, pages 279--284, 1988. > >2. The Karp-Lipton paper "Some connections between nonuniform > and uniform complexity classes." I only have a reference > to the STOC '80 version. Yes, there is a journal version (thanks to E. Allender). It's published in a strange place, L'Enseignment Mathematique. It was apparently a special issue that also included an article by Borodin on Models of Computation. The full citation is: "Turing Machines that Take Advice", L'Enseignement Math\'ematique, volume 28, pages 191--209, 1982. Thanks to all who replied. Richard