Recognition of deterministic ETOL languages in logarithmic space

Information and Control - Tập 35 - Trang 177-181 - 1977
Neil D. Jones1, Sven Skyum1
1Computer Science Department, University of Aarhus, 8000 Aarhus C, Denmark

Tài liệu tham khảo

Herman, 1975 Hopcroft, 1969 Nielsen, 1974, Nonterminals, homomorphisms and codings in different variations of OL systems, I. Deterministic systems, Acta Informatica, 4, 87, 10.1007/BF00288938 Opatrný, 1975, Time complexity of L-languages Salomaa, 1973 Salomaa, 1974, Parallelism in rewriting systems Skyum, 1974, Parallel context-free languages, Inform. Contr., 26, 280, 10.1016/S0019-9958(74)91399-0 Sudborough, 1975, A note on tape-bounded complexity classes and linear contextfree languages, J. Assoc. Comput. Mach., 22, 499, 10.1145/321906.321913 Sudborough, 1976, The complexity of the membership problem for some extensions of context-free languages, 60201 van Leeuwen, 1975, The membership question for ETOL languages is polynomially complete, 3, 138 van Leeuwen, 1975, The tape complexity of context-independent developmental languages, J. Comp. System Sci., 11, 203, 10.1016/S0022-0000(75)80068-7