{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:19Z","timestamp":1725663259220},"publisher-location":"Berlin, Heidelberg","reference-count":73,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540083535"},{"type":"electronic","value":"9783540372851"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08353-7_136","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:23:20Z","timestamp":1330187000000},"page":"177-191","source":"Crossref","is-referenced-by-count":0,"title":["Properties of complexity classes a short survey"],"prefix":"10.1007","author":[{"given":"Gerd","family":"Wechsung","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"14_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"Aho, A. V., Hopcroft, J. E., Ullman, J. D., The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974."},{"key":"14_CR2","first-page":"10","volume":"5","author":"A. S. Barashko","year":"1976","unstructured":"Barashko, A. S., Roizen, S. I., Kernels of partial recursive functions naming complexity classes. Kibernetika (Kiev) 5 (1976) 10\u201315.","journal-title":"Kibernetika (Kiev)"},{"issue":"4","key":"14_CR3","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0201019","volume":"1","author":"R. V. Book","year":"1972","unstructured":"Book, R. V., On languages accepted in polynomial time. SIAM J. Comp. 1,4 (1972) 281\u2013287.","journal-title":"SIAM J. Comp."},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R. V. Book","year":"1974","unstructured":"Book, R. V., Tally languages and complexity classes. Inf. and Contr. 26 (1974) 186\u2013193.","journal-title":"Inf. and Contr."},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0304-3975(76)90057-8","volume":"1","author":"R. V. Book","year":"1976","unstructured":"Book, R. V., Translational lemmas, polynomial time and (logn)j-space. TCS 1 (1976) 215\u2013226.","journal-title":"TCS"},{"key":"14_CR6","first-page":"622","volume":"4","author":"R. V. Book","year":"1970","unstructured":"Book, R. V., Greibach, S. A., Ibarra, O. H., Wegbreit, B., Tape bounded Turing acceptors and principal AFL. JCSS 4 (1970) 622\u2013625.","journal-title":"JCSS"},{"key":"14_CR7","first-page":"606","volume":"4","author":"R. V. Book","year":"1970","unstructured":"Book, R. V., Greibach, S. A., Wegbreit, B., Time and tape bounded Turing acceptors and AFLs. JCSS 4 (1970) 606\u2013621.","journal-title":"JCSS"},{"key":"14_CR8","first-page":"76","volume":"12","author":"M. P. Chytil","year":"1976","unstructured":"Chytil, M. P., Crossing-bounded computations and their relation to LBA-problem. Kybernetika 12 (1976) 76\u201385.","journal-title":"Kybernetika"},{"key":"14_CR9","first-page":"230","volume":"45","author":"M. P. Chytil","year":"1976","unstructured":"Chytil, M. P., Analysis of the non-context-free component of formal languages. LNCS 45 (1976) 230\u2013236.","journal-title":"LNCS"},{"key":"14_CR10","unstructured":"Cobham, A., The intrinsic computational difficulty of functions. Proc. Int. Congr. Logic, Methodology a. Philosophie of Science 1964, North Holland, Amsterdam 1965, 24\u201330."},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Constable, R. L., Type two computational complexity. Proc. 5th Ann. ACM Symp. Theory of Comput. (1973) 108\u2013121.","DOI":"10.1145\/800125.804041"},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. A. Cook","year":"1971","unstructured":"Cook, S. A., Characterizations of pushdown machines in terms of time bounded computers. JACM 18,1 (1971) 4\u201318.","journal-title":"JACM"},{"key":"14_CR13","unstructured":"Cook, S. A., Linear time simulation of deterministic two-way pushdown automata. In: Information processing 71 (Proc. IFIP Congress Ljubljana 1971), Vol. 1, pp. 75\u201380. Amsterdam 1972."},{"key":"14_CR14","first-page":"389","volume":"6","author":"H. Enderton","year":"1972","unstructured":"Enderton, H., Degrees of computational complexity. JCSS 6 (1972) 389\u2013396.","journal-title":"JCSS"},{"issue":"3","key":"14_CR15","first-page":"265","volume":"2","author":"P. C. Fischer","year":"1968","unstructured":"Fischer, P. C., Meyer, A. R., Rosenberg, A. L., Counter machines and counter languages. MST 2,3 (1968) 265\u2013283.","journal-title":"MST"},{"key":"14_CR16","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF00263744","volume":"6","author":"Z. Galil","year":"1976","unstructured":"Galil, Z., Hierarchies of complete problems. Acta Inf. 6 (1976) 77\u201388.","journal-title":"Acta Inf."},{"key":"14_CR17","unstructured":"Ginsburg, S., Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland Amsterdam, 1975."},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/0020-0255(70)90037-X","volume":"2","author":"S. Ginsburg","year":"1970","unstructured":"Ginsburg, S., Rose, G., On the existence of generators for certain AFL. Inform. Sci. 2(1970) 431\u2013446.","journal-title":"Inform. Sci."},{"key":"14_CR19","first-page":"168","volume":"6","author":"J. A. Giuliano","year":"1972","unstructured":"Giuliano, J. A., Writing stack acceptors. JCSS 6 (1972) 168\u2013204.","journal-title":"JCSS"},{"key":"14_CR20","first-page":"25","volume":"4","author":"Ju. V. Glebski","year":"1971","unstructured":"Glebski, Ju. V., Kogan, D. I., Additive control systems and languages some algorithmic problems. Kibernetika (Kiev) 4 (1971) 25\u201329.","journal-title":"Kibernetika (Kiev)"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Graham, S. L., Harrison, M. A., Ruzzo, W. L., On line context-free language recognition in less than cubic time. Proc. 8th Ann. ACM Symp. Theory of Comput., Hershey 1976, 112\u2013120.","DOI":"10.1145\/800113.803638"},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. A. Greibach","year":"1973","unstructured":"Greibach, S. A., The hardest context-free language. SIAM J. Comp. 2 (1973) 304\u2013310.","journal-title":"SIAM J. Comp."},{"issue":"2","key":"14_CR23","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1145\/321450.321464","volume":"15","author":"J. Hartmanis","year":"1968","unstructured":"Hartmanis, J., Computational complexity of one-tape Turing machine computations. JACM 15,2 (1968) 325\u2013339.","journal-title":"JACM"},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J. Hartmanis","year":"1972","unstructured":"Hartmanis, J., On non-determinacy in simple computing devices. Acta Inf. 1(1972) 336\u2013344.","journal-title":"Acta Inf."},{"key":"14_CR25","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1145\/321650.321661","volume":"18","author":"J. Hartmanis","year":"1971","unstructured":"Hartmanis, J., Hopcroft, J. E., An overview of the theory of computational complexity. JACM 18 (1971) 444\u2013475.","journal-title":"JACM"},{"key":"14_CR26","first-page":"1","volume":"7","author":"J. Hartmanis","year":"1974","unstructured":"Hartmanis, J., Hunt III, H. B., The LBA problem and its importance in the theory of computing. SIAM-AMS proceedings, vol. 7 (1974) 1\u201326.","journal-title":"SIAM-AMS proceedings"},{"key":"14_CR27","first-page":"1","volume-title":"Advances in Computers, vol. 14","author":"J. Hartmanis","year":"1976","unstructured":"Hartmanis, J., Simon, J., On the structure of feasible computations. In: Advances in Computers, vol. 14, pp. 1\u201343. Academic Press, New York, 1976."},{"issue":"6","key":"14_CR28","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F. C. Hennie","year":"1965","unstructured":"Hennie, F. C., One-tape off-line Turing machine computations. Information and Control 8,6 (1965) 553\u2013578.","journal-title":"Information and Control"},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"Hopcroft, J., Paul, W., Valiant, L., On time versus space and related problems. 16th Ann. Symp. on Found. of Comp. Sc. 1975, 57\u201364.","DOI":"10.1109\/SFCS.1975.23"},{"issue":"2","key":"14_CR30","first-page":"166","volume":"1","author":"J. E. Hopcroft","year":"1967","unstructured":"Hopcroft, J. E., Ullman, J. D., Nonerasing stack automata. JCSS 1,2 (1967) 166\u2013186.","journal-title":"JCSS"},{"issue":"5","key":"14_CR31","first-page":"384","volume":"5","author":"J. Ho\u0159ej\u0161","year":"1969","unstructured":"Ho\u0159ej\u0161, J., Recursive functions computable within Cflogf. Kibernetika 5,5 (1969) 384\u2013398.","journal-title":"Kibernetika"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Hunt III, H. B., On the time and tape complexity of languages I. Proc. 5th Ann. A CM Symp. Theory of Comput. 1973, 10\u201319.","DOI":"10.1145\/800125.804030"},{"key":"14_CR33","first-page":"88","volume":"5","author":"O. H. Ibarra","year":"1971","unstructured":"Ibarra, O. H., Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata. JCSS 5 (1971) 88\u2013117.","journal-title":"JCSS"},{"key":"14_CR34","unstructured":"Jones, N. D., Reducibility among combinatorial problems in log n space. Proc. 7th Ann. Princeton Conf. on Information Sciences and Systems 1973, 547\u2013551."},{"issue":"1","key":"14_CR35","first-page":"139","volume":"39","author":"N. D. Jones","year":"1974","unstructured":"Jones, N.D., Selman, A. L., Turing machines and the spectra of first-order formulas. JSL 39, 1 (1974) 139\u2013150.","journal-title":"JSL"},{"key":"14_CR36","unstructured":"Kameda, T., Constant-tape-reversal bounded Turing machine computations. Proc. Intern. Computing Symposium 1970, Bonn, 649\u2013654."},{"key":"14_CR37","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R. M. Karp","year":"1975","unstructured":"Karp, R. M., On the computational complexity of combinatorial problems. Networks 5 (1975) 45\u201368.","journal-title":"Networks"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"Ladner, R. E., Polynomial time reducibility. Proc. 5th Ann. ACM Symp. Theory of Comput. 1973, 122\u2013129.","DOI":"10.1145\/800125.804042"},{"key":"14_CR39","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"Ladner, R. E., Lynch, N. A., Selman, A. L., A comparison of polynomial time reducibilities. TCS 1 (1975) 103\u2013123.","journal-title":"TCS"},{"issue":"1","key":"14_CR40","first-page":"122","volume":"12","author":"F. D. Lewis","year":"1976","unstructured":"Lewis, F. D., On computational reducibility. JCSS 12,1 (1976) 122\u2013131.","journal-title":"JCSS"},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"Lewis, II, P. M., Stearns, R. E., Hartmanis, J., Memory bounds for recognition of context-free and contextsensitive languages. IEEE Conf. Rec. Switch. Circuit Theory and Logig Design pp. 191\u2013202, New York, 1965.","DOI":"10.1109\/FOCS.1965.14"},{"key":"14_CR42","unstructured":"Lind, J. C., Computing in logarithmic space. MAC MEM 52, MIT, 1974."},{"key":"14_CR43","first-page":"276","volume":"3","author":"G. Mager","year":"1969","unstructured":"Mager, G., Writing pushdown acceptors, JCSS 3 (1969) 276\u2013318.","journal-title":"JCSS"},{"key":"14_CR44","volume-title":"Classes of computable functions defined by bounds on computation","author":"E. M. Mc Creight","year":"1969","unstructured":"Mc Creight, E. M., Classes of computable functions defined by bounds on computation. Diss., Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1969."},{"issue":"2","key":"14_CR45","first-page":"147","volume":"12","author":"K. Mehlhorn","year":"1976","unstructured":"Mehlhorn, K., Polynomial and abstract subrecursive classes. JCSS 12,2 (1976) 147\u2013178.","journal-title":"JCSS"},{"key":"14_CR46","doi-asserted-by":"crossref","unstructured":"Meyer, A. R., Stockmeyer, L. J., Word problems requiring exponential time. Proc. 5th Ann. ACM Symp. Theory of Computing 1973) 1\u20139.","DOI":"10.1145\/800125.804029"},{"key":"14_CR47","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0304-3975(76)90055-4","volume":"1","author":"R. Moll","year":"1976","unstructured":"Moll, R., An operator imbedding theorem for complexity classes of recursive functions. TCS 1 (1976) 193\u2013198.","journal-title":"TCS"},{"key":"14_CR48","first-page":"280","volume":"14","author":"B. Monien","year":"1974","unstructured":"Monien, B., Characterization of time bounded computations by limited primitive recursion. LNCS 14 (1974) 280\u2013293.","journal-title":"LNCS"},{"key":"14_CR49","first-page":"248","volume":"9","author":"B. Monien","year":"1975","unstructured":"Monien, B., Relationships between pushdown automata with counters and complexity classes. MST 9 (1975) 248\u2013264.","journal-title":"MST"},{"key":"14_CR50","first-page":"118","volume":"33","author":"B. Monien","year":"1975","unstructured":"Monien, B., About the simulation of nondeterministic log n-tape bounded Turing machines. LNCS 33 (1975) 118\u2013126.","journal-title":"LNCS"},{"key":"14_CR51","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0304-3975(76)90065-7","volume":"3","author":"B. Monien","year":"1977","unstructured":"Monien, B., A recursive and grammatical characterization of the exponential time languages. TCS 3 (1977) 61\u201374.","journal-title":"TCS"},{"key":"14_CR52","first-page":"29","volume":"2","author":"V. A. Nepomnyashchi","year":"1970","unstructured":"Nepomnyashchi, V. A., A rudimentary interpretation of two-tape Turing computations. Kibernetika (Kiev) 2 (1970) 29\u201335.","journal-title":"Kibernetika"},{"key":"14_CR53","first-page":"64","volume":"5","author":"V. A. Nepomnyashchi","year":"1975","unstructured":"Nepomnyashchi, V. A., On tape complexity for recognition of context-free languages. Kibernetika (Kiev) 5 (1975) 64\u201368.","journal-title":"Kibernetika"},{"key":"14_CR54","first-page":"116","volume":"6","author":"M. S. Paterson","year":"1972","unstructured":"Paterson, M. S., Tape bounds for time bounded Turing machines. JCSS 6 (1972) 116\u2013124.","journal-title":"JCSS"},{"key":"14_CR55","unstructured":"Peckel, J., On a deterministic subclass of context-free languages. This volume."},{"key":"14_CR56","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0019-9958(72)90205-7","volume":"20","author":"R. Ritchie","year":"1972","unstructured":"Ritchie, R., Springsteel, F. N., Language recognition by marking automata. Inf. and Contr. 20 (1972) 313\u2013330.","journal-title":"Inf. and Contr."},{"key":"14_CR57","first-page":"69","volume":"9","author":"E. L. Robertson","year":"1974","unstructured":"Robertson, E. L., Complexity classes of partial recursive functions. JCSS 9 (1974) 69\u201387.","journal-title":"JCSS"},{"issue":"4","key":"14_CR58","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1145\/321420.321423","volume":"14","author":"A. L. Rosenberg","year":"1967","unstructured":"Rosenberg, A. L., Real-time definable languages. JACM 14, 4 (1967) 645\u2013662.","journal-title":"JACM"},{"key":"14_CR59","doi-asserted-by":"crossref","unstructured":"Rounds, W. C., A grammatical characterization of exponential time languages. 16th Ann. Symp. on Found. of Computer Sc. (1975) 135\u2013143.","DOI":"10.1109\/SFCS.1975.1"},{"key":"14_CR60","first-page":"177","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"Savitch, W. J., Relationship between nondeterministic and deterministic tape complexities. JCSS 4 (1970) 177\u2013192.","journal-title":"JCSS"},{"key":"14_CR61","doi-asserted-by":"crossref","unstructured":"Schaefer, T. J., Complexity of decision problems based on finite two-person perfect-information games. 8th. Ann. ACM Symp. Theory of Computing (1976) 41\u201349.","DOI":"10.1145\/800113.803629"},{"key":"14_CR62","first-page":"27","volume":"14","author":"E. Shamir","year":"1974","unstructured":"Shamir, E., Beeri, C., Checking stacks and context-free programmed grammars accept p-complete languages. LNCS 14 (1974) 27\u201333.","journal-title":"LNCS"},{"key":"14_CR63","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/S0019-9958(71)90501-8","volume":"18","author":"A. R. Smith III","year":"1971","unstructured":"Smith III, A.R., Cellular automata complexity trade-offs. Inf. and Control 18 (1971) 466\u2013482.","journal-title":"Inf. and Control"},{"key":"14_CR64","doi-asserted-by":"crossref","unstructured":"Specker, E., Strassen, V., Komplexit\u00e4t von Entscheidungsproblemen. LNCS 43, Springer Verlag 1976.","DOI":"10.1007\/3-540-07805-3"},{"key":"14_CR65","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0304-3975(76)90082-7","volume":"2","author":"F. N. Springsteel","year":"1976","unstructured":"Springsteel, F. N., On the pre-AFL of logn space and related families of languages. TCS 2 (1976) 295\u2013304.","journal-title":"TCS"},{"key":"14_CR66","first-page":"179","volume-title":"IEEE Conf. Rec. Switch. Circuit Theory and Logic","author":"R. E. Stearns","year":"1965","unstructured":"Stearns, R. E., Hartmanis, J., Lewis II, P. M., Hierarchies of memory limited computations. IEEE Conf. Rec. Switch. Circuit Theory and Logic. Design, New York 1965, 179\u2013190."},{"key":"14_CR67","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L. J., The polynomial-time hierarchy. TCS 3 (1977) 1\u201322.","journal-title":"TCS"},{"key":"14_CR68","first-page":"62","volume":"10","author":"I. H. Sudborough","year":"1975","unstructured":"Sudborough, I. H., On tape-bounded complexity classes and multihead finite automata. JCSS 10 (1975) 62\u201376.","journal-title":"JCSS"},{"issue":"4","key":"14_CR69","first-page":"33","volume":"3","author":"B. A. Trachtenbrot","year":"1964","unstructured":"Trachtenbrot, B. A., Turing computations with logarithmic delay. Algebra i Logika 3, 4 (1964) 33\u201348.","journal-title":"Algebra i Logika"},{"key":"14_CR70","first-page":"289","volume":"12","author":"G. Wechsung","year":"1976","unstructured":"Wechsung, G., Kompliziertheitstheoretische Charakterisierung der kontextfreien und linearen Sprachen. EIK 12 (1976) 289\u2013300.","journal-title":"EIK"},{"key":"14_CR71","unstructured":"Weihrauch, K., Teilklassen primitiv-rekursiver Wortfunktionen. Ges. f. Mathematik und Datenverarbeitung, Bonn 1974, Nr. 91."},{"key":"14_CR72","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"Wrathall, C., Complete sets and the polynomial-time hierarchy. TCS 3 (1977) 23\u201333.","journal-title":"TCS"},{"issue":"2","key":"14_CR73","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D. H. Younger","year":"1967","unstructured":"Younger, D. H., Recognition and parsing of context-free languages in time n3. Inf. and Contr. 10, 2 (1967) 189\u2013208.","journal-title":"Inf. and Contr."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1977"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08353-7_136.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:59:20Z","timestamp":1605643160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08353-7_136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083535","9783540372851"],"references-count":73,"URL":"https:\/\/doi.org\/10.1007\/3-540-08353-7_136","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}