{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T20:09:27Z","timestamp":1648670967753},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1981,12,1]],"date-time":"1981-12-01T00:00:00Z","timestamp":376012800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1981,12]]},"DOI":"10.1007\/bf01752398","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T10:43:16Z","timestamp":1118832196000},"page":"223-227","source":"Crossref","is-referenced-by-count":0,"title":["A note on context free languages, complexity classes, and diagonalization"],"prefix":"10.1007","volume":"14","author":[{"given":"F. D.","family":"Lewis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01752398_CR1","unstructured":"A. K. Arora and I. H. Sudborough, On languages log-tape reducible to context-free languages,Proc. 1976 Conf. on Infor. Sci. and Systems, The Johns Hopkins University, 27\u201332."},{"key":"BF01752398_CR2","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem proving procedures,Proc. 3rd ACM Sym. on Theory of Comput. (1971), 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF01752398_CR3","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. A. Greibach","year":"1973","unstructured":"S. A. Greibach, The hardest context free language,SIAM J. on Comput. 2, 304\u2013310, (1973).","journal-title":"SIAM J. on Comput."},{"key":"BF01752398_CR4","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1145\/321450.321464","volume":"15","author":"J. Hartmanis","year":"1968","unstructured":"J. Hartmanis, Computational complexity of one-tape Turing machine computation,J. Assoc. for Comput. Mach. 15, 325\u2013339, (1968).","journal-title":"J. Assoc. for Comput. Mach."},{"key":"BF01752398_CR5","volume-title":"Formal Languages and their Relation to Automata","author":"J. E. Hopcroft","year":"1969","unstructured":"J. E. Hopcroft and J. D. Ullman,Formal Languages and their Relation to Automata, Addison-Wesley, Reading, MA 1969."},{"key":"BF01752398_CR6","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1975","unstructured":"N. D. Jones, Space bounded reducibility and combinatorial problems,J. Comput. and System Sci. 11, 68\u201385, (1975).","journal-title":"J. Comput. and System Sci."},{"key":"BF01752398_CR7","unstructured":"F. D. Lewis, Algorithmic classes of functions and fixed points, Tech. Rpt. 10\u201373, Ctr. for Research in Comput. Tech., Harvard University (1973)."},{"key":"BF01752398_CR8","unstructured":"F. D. Lewis, Subrecursive reducibilities and completeness,Proc. 1976 Conf. on Infor. Sci. and Systems, The John Hopkins University, 36\u201341."},{"key":"BF01752398_CR9","doi-asserted-by":"crossref","unstructured":"P. M. Lewis, R. E. Stearns, and J. Hartmanis, Memory bounds for recognition of context free languages,IEEE Conf. on Switch. Theory and Logical Design (1965), 191\u2013202.","DOI":"10.1109\/FOCS.1965.14"},{"key":"BF01752398_CR10","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1002\/malq.19550010205","volume":"1","author":"J. Myhill","year":"1955","unstructured":"J. Myhill, Creative Sets,Zeit. f. Math. Logik u. Grund. d. Math. 1, 97\u2013108, (1955).","journal-title":"Zeit. f. Math. Logik u. Grund. d. Math."},{"key":"BF01752398_CR11","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E. L. Post","year":"1944","unstructured":"E. L. Post, Recursively enumerable sets of positive integers and their decision problems,Bull. AMS 50, 284\u2013316, (1944).","journal-title":"Bull. AMS"},{"key":"BF01752398_CR12","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"H. Rogers, Jr.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, NY, 1967."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01752398.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01752398\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01752398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T18:56:48Z","timestamp":1586285808000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01752398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,12]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1981,12]]}},"alternative-id":["BF01752398"],"URL":"https:\/\/doi.org\/10.1007\/bf01752398","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,12]]}}}