The membership question for ETOL-languages is polynomially complete. (English) Zbl 0309.68065


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Aho, A. V.; Ullman, J. D., The theory of parsing, translating and compiling, vol. I (1972), Prentice Hall: Prentice Hall Englewood Cliffs, N.J · Zbl 0264.68032
[2] Cobham, A., The intrinsic computational difficulty of functions, (Bar-hillel, Y., Proc. 1964 Intern. Congress on Logic, Methodology, and Philosophy of Science (1965), North-Holland Publ. Comp: North-Holland Publ. Comp Amsterdam), 24-30 · Zbl 0192.08702
[3] Cook, S. A., The complexity of theorem-proving procedures, Proc. 3rd Annual ACM Symp. on Theory of Computing, 151-158 (1971) · Zbl 0253.68020
[4] Culik, K., On some families of languages related to developmental systems, (Techn. Rep. CS-73-12 (1973), Dept. of Appl. Analysis and Computer Science: Dept. of Appl. Analysis and Computer Science Waterloo, Canada) · Zbl 0294.68025
[5] Herman, G. T.; Rozenberg, G., Developmental systems and languages (1975), North-Holland Publ. Comp: North-Holland Publ. Comp Amsterdam · Zbl 0313.68068
[6] A. Ehronfeucht, G. Rozenberg and S. Skyum, A relationship between ETOL and EDTOL languages, Theor. Computer Science (to appear).; A. Ehronfeucht, G. Rozenberg and S. Skyum, A relationship between ETOL and EDTOL languages, Theor. Computer Science (to appear). · Zbl 0339.68055
[7] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1973), Plenum Press: Plenum Press New York), 85-104 · Zbl 0366.68041
[8] Knuth, D. E., A terminological proposal, SIGACT NEWS 6, 12-18 (January 1974), (see also SIGACT NEWS 6, April 1974, 15-16)
[9] Rosenkrantz, D. J., Programmed grammars and classes of formal languages, JACM, 16, 107-131 (1969) · Zbl 0182.02004
[10] Rounds, W. C., Complexity of intermediate level languages, Conf. Record 14th Ann. Symp. on Switching and Automata Theory, 145-158 (1973), Iowa
[11] Rozenberg, G., TOL systems and languages, Inform. and Control, 23, 357-381 (1973) · Zbl 0273.68055
[12] Rozenberg, G., Personal communication (1974)
[13] Salomaa, A., Formal Languages (1973), Acad. Press: Acad. Press New York · Zbl 0262.68025
[14] Shamir, E.; Beeri, C.; Loeckx, J., Proc. 2nd Colloquium on Automata, Languages, and Programming, Springer Lecture Notes in Computer Science, 14, 27-33 (1974), Checking stacks and context-free programmed grammars accept \(p\)-complete languages · Zbl 0294.68028
[15] Van Leeuwen, J., External properties of non-deterministic time-complexity classes, (Proc. Intern. Computing Symposium (1975), North-Holland Publ. Comp), to appear · Zbl 0324.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.