Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
Krause, M. ; Meinel, Ch. ; Waack, St.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992), p. 345-362 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1992-01-01
@article{ITA_1992__26_4_345_0,
     author = {Krause, M. and Meinel, Ch. and Waack, St.},
     title = {Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {26},
     year = {1992},
     pages = {345-362},
     mrnumber = {1173174},
     zbl = {0768.68017},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1992__26_4_345_0}
}

Krause, M.; Meinel, Ch.; Waack, St. Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992) pp. 345-362. http://gdmltest.u-ga.fr/item/ITA_1992__26_4_345_0/

[AM86] N. Alon and W. Maass, Meanders, Ramsey Theory and Lower Bounds, Proc. 27th I.E.E.E. FOCS 410-417, 1986.

[Im87] N. Immerman, Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale Univ., 1987. | MR 961049

[KL80] R. M. Karp and R. J. Lipton, Some Connections Between Nonuniform and Uniform Complexity Classes, Proc. 12th A.C.M. Symp. on Theory of Computing, 302-309 1980.

[KMW91] M. Krause, Ch. Meinel and S. Waack, Separating the Eraser Turing Machine Classes Le, NLe, co-NLe and Pe, Theoret. Comput. Sci., 1991, 86, pp. 267-275. | MR 1122791 | Zbl 0749.68036

[Kr91] M. Krause, Lower Bounds for Depth-Restricted Branching programs, Inform. and Comput., 1991, 91, pp. 1-14. | MR 1097261 | Zbl 0800.68495

[KW91] M. Krause and S. Waack, On Oblivious Branching Programs of Linear Length, Inform. and Comput., 1991, 94, pp. 232-249. | MR 1127534 | Zbl 0727.68038

[Me86] Ch. Meinel, p-Projection Reducibility and the Complexity Classes L (Nonuniform) and NL (Nonuniform), Proc. 12th MFCS, Bratislava, LNCS 233, pp.527-535; revised and extended version in EIK, 1987, 23, 10/11, pp. 545-558. | MR 935269 | Zbl 0611.03021

[Me88] Ch. Meinel, The Power of Polynomial Size Ω-Branching Programs, Proc. STAC'88, Bordeaux, L.N.C.S. n° 294, pp. 81-90. | MR 935789 | Zbl 0644.68074

[Ru81] W. Ruzzo, On Uniform Circuit Complexity, J. Comput. System Sci., 1981, 22, (3), pp. 236-283. | MR 633540 | Zbl 0462.68013

[SV81] S. Skyum and L. Valiant, A Complexity Theory Based on Boolean Algebra, Proc. 22th LE.E.E. F.O.C.S., 1981, pp. 244-253.

[Sz87] R. Szelepcsenyi, The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. | Zbl 0664.68082

[We87] I. Wegener, The Complexity of Boolean Functions, Teubner, Stuttgart, 1987. | MR 905473 | Zbl 0623.94018