zbMATH — the first resource for mathematics

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 Englewood Cliffs, N.J · Zbl 0264.68032
[2] Cobham, A., The intrinsic computational difficulty of functions, (), 24-30
[3] Cook, S.A., The complexity of theorem-proving procedures, Proc. 3rd annual ACM symp. on theory of computing, 151-158, (1971)
[4] Culik, K., On some families of languages related to developmental systems, () · Zbl 0294.68025
[5] Herman, G.T.; Rozenberg, G., Developmental systems and languages, (1975), 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). · Zbl 0339.68055
[7] Karp, R.M., Reducibility among combinatorial problems, (), 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 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
[15] Van Leeuwen, J., External properties of non-deterministic time-complexity classes, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.