{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:46:41Z","timestamp":1725662801694},"publisher-location":"Berlin, Heidelberg","reference-count":22,"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_172","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:25:57Z","timestamp":1330187157000},"page":"493-503","source":"Crossref","is-referenced-by-count":12,"title":["Time and tape bounded auxiliary pushdown automata"],"prefix":"10.1007","author":[{"given":"I. H.","family":"Sudborough","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"50_CR1","unstructured":"Sudborough, I.H., On the tape complexity of deterministic context-free languages, to appear in Journal of Assoc. for Comput. Mach."},{"key":"50_CR2","doi-asserted-by":"crossref","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, Journal of Assoc. for Comput. Mach. 18 (1971), 4\u201318.","journal-title":"Journal of Assoc. for Comput. Mach."},{"key":"50_CR3","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1975","unstructured":"Jones, N.D., Space bounded reducibility among combinatorial problems, Journal of Comput. and System Sci. 11 (1975), 62\u201385.","journal-title":"Journal of Comput. and System Sci."},{"key":"50_CR4","doi-asserted-by":"crossref","unstructured":"Meyer, A.R. and L.J. Stockmeyer, Word problems requiring exponential time, in Proceedings of Fifth Annual Assoc. for Comput. Mach. Symposium on Theory of Computing (1973), 1\u20139. Association for Computing Machinery, 1133 Avenue of the Americas, New York.","DOI":"10.1145\/800125.804029"},{"key":"50_CR5","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 Journal on Computing 2 (1973), 304\u2013310.","journal-title":"SIAM Journal on Computing"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Sudborough, I.H., Separating tape bounded auxiliary pushdown automata classes, to appear in Proceedings of Ninth Annual Assoc. for Comput. Mach. Symposium on Theory of Computing (1977). (See reference 4 for address of ACM.)","DOI":"10.1145\/800105.803410"},{"key":"50_CR7","volume-title":"The Theory of Parsing, Translation, and Compiling, vols. I and II","author":"A. V. Aho","year":"1972","unstructured":"Aho, A.V. and J.D. Ullman, The Theory of Parsing, Translation, and Compiling, vols. I and II, Prentice-Hall Publishing Co., Englewood Cliffs, New Jersey, U.S.A., 1972 and 1973."},{"key":"50_CR8","unstructured":"Sudborough, I.H., The complexity of the membership problem for some extensions of context-free languages, to appear in International Journal of Computer Math."},{"key":"50_CR9","doi-asserted-by":"crossref","unstructured":"Sudborough, I.H., The time and tape complexity of developmental languages, to appear in Proceedings of Fourth International Conference on Automata, Languages, and Programming, to be held in Turku, Finland (July 18\u201322, 1977). (The proceedings will be published in the Lecture Notes in Computer Science Series, Springer-Verlag Publishing Co., New York.)","DOI":"10.1007\/3-540-08342-1_40"},{"key":"50_CR10","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/S0022-0000(70)80045-9","volume":"4","author":"T. Kasai","year":"1970","unstructured":"Kasai, T., An hierarchy between context-free and context-sensitive languages, Journal of Computer and System Sci. 4 (1970), 492\u2013508.","journal-title":"Journal of Computer and System Sci."},{"key":"50_CR11","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/S0022-0000(74)80053-X","volume":"8","author":"A. B. Cremers","year":"1974","unstructured":"Cremers, A.B. and O. Mayer, On vector languages, Journal of Computer and System Sci. 8 (1974), 142\u2013157.","journal-title":"Journal of Computer and System Sci."},{"key":"50_CR12","doi-asserted-by":"crossref","unstructured":"Lewis, P.M., R.E. Stearns, and J. Hartmanis, Memory bounds for the recognition of context-free and context-sensitive languages, in Proceedings of the Sixth Annual IEEE Symposium on Switching Circuit Theory and Logical Design (1965), 199\u2013212. (copies available from IEEE Computer Society, 5855 Naples Plaza, Suite 301, Long Beach, California, U.S.A.)","DOI":"10.1109\/FOCS.1965.14"},{"key":"50_CR13","doi-asserted-by":"crossref","unstructured":"Cook, S.A., The complexity of theorem proving procedures, in Proceedings of the third Annual Assoc. for Comput. Mach. Symposium on Theory of Computing (1971), 151\u2013158. (See reference 4 for address of ACM.)","DOI":"10.1145\/800157.805047"},{"key":"50_CR14","volume-title":"Complexity of Computer Computation","author":"R. M. Karp","year":"1972","unstructured":"Karp, R.M., Reducibilities among combinatorial problems, in Complexity of Computer Computation (R. Miller and J. Thatcher, Eds.), Plenum Publishing Company, New York, 1972."},{"key":"50_CR15","unstructured":"Jones, N.D. and W.T. Laaser, Problems complete for deterministic polynomial time, to appear in Theoretical Computer Science. (A preliminary version appears in the Proceedings of the Sixth Annual ACM Symposium on Theory of Computing; see reference 4 for address information)"},{"key":"50_CR16","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S. A. Cook","year":"1974","unstructured":"Cook, S.A., On observation on time-storage trade-off, Journal of Computer and System Sci. 9 (1974), 308\u2013316.","journal-title":"Journal of Computer and System Sci."},{"key":"50_CR17","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I. H. Sudborough","year":"1975","unstructured":"Sudborough, I.H., On tape bounded complexity classes and multihead finite automata, Journal of Computer and System Sci. 10 (1975), 62\u201376.","journal-title":"Journal of Computer and System Sci."},{"key":"50_CR18","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1145\/321906.321913","volume":"22","author":"I. H. Sudborough","year":"1975","unstructured":"Sudborough, I.H., On tape bounded complexity classes and linear context-free languages, Journal of Assoc. for Comput. Mach. 22 (1975), 500\u2013501.","journal-title":"Journal of Assoc. for Comput. Mach."},{"key":"50_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N. D. Jones","year":"1976","unstructured":"Jones, N.D., Y.E. Lien and W.T. Laaser, New problems complete for nondeterministic log space, Mathematical Systems Theory 10 (1976), 1\u201317.","journal-title":"Mathematical Systems Theory"},{"key":"50_CR20","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Path systems and language recognition, in Proceedings of Second Annual ACM Symposium on Theory of Computing (1970), 70\u201372. (See reference 4 for address information.)","DOI":"10.1145\/800161.805151"},{"key":"50_CR21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sci. 4 (1970), 177\u2013192.","journal-title":"Journal of Computer and System Sci."},{"key":"50_CR22","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. E. Ladner","year":"1976","unstructured":"Ladner, R.E. and N.A. Lynch, Relativization of questions about log space computability, Mathematical Systems Theory 10 (1976), 19\u201332.","journal-title":"Mathematical Systems Theory"}],"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_172.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:59:26Z","timestamp":1605643166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08353-7_172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083535","9783540372851"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-08353-7_172","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}