{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:14Z","timestamp":1725662894926},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540133452"},{"type":"electronic","value":"9783540388869"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1984]]},"DOI":"10.1007\/3-540-13345-3_22","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:02:28Z","timestamp":1330192948000},"page":"247-259","source":"Crossref","is-referenced-by-count":3,"title":["Space and time efficient simulations and characterizations of some restricted classes of PDAS"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam M.","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis E.","family":"Rosier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Braunmuhl, B. and Verbeek, R., A recognition algorithm for deterministic CFLs optimal in time and space, Proc. 21st IEEE-FOCS, pp. 411\u2013420 (1980).","DOI":"10.1109\/SFCS.1980.8"},{"key":"22_CR2","first-page":"308","volume":"9","author":"S. Cook","year":"1974","unstructured":"Cook, S., An observation on time-storage tradeoff, JCSS, Vol. 9, pp. 308\u2013316 (1974).","journal-title":"JCSS"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S., Deterministic CFL's are accepted simultaneously in polynomial time and log squared space, Proc. 11th ACM Symp. on Theory of Comp., pp. 338\u2013345 (1979).","DOI":"10.1145\/800135.804426"},{"issue":"3","key":"22_CR4","first-page":"265","volume":"2","author":"P. Fischer","year":"1968","unstructured":"Fischer, P., Meyer, A. and Rosenberg, A., Counter machines and counter languages, MST, Vol. 2, No. 3, pp. 265\u2013283 (1968).","journal-title":"MST"},{"key":"22_CR5","first-page":"211","volume":"10","author":"Z. Galil","year":"1977","unstructured":"Galil, Z., Two-way deterministic pushdown automaton languages and some open problems in the theory of computing, MST, Vol. 10, pp. 211\u2013228 (1977).","journal-title":"MST"},{"key":"22_CR6","first-page":"1","volume":"1","author":"S. Ginsburg","year":"1967","unstructured":"Ginsburg, S. and Harrison, M., Backeted context-free languages, JCSS, Vol. 1, pp. 1\u201323 (1967).","journal-title":"JCSS"},{"key":"22_CR7","first-page":"196","volume":"3","author":"S. Greibach","year":"1969","unstructured":"Greibach, S., Checking automata and one-way stack languages, JCSS, Vol. 3, pp. 196\u2013217 (1969).","journal-title":"JCSS"},{"issue":"2","key":"22_CR8","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0209029","volume":"9","author":"E. Gurari","year":"1980","unstructured":"Gurari, E. and Ibarra, O., Path systems: constructions, solutions and applications, SIAM J. Comput., Vol. 9, No. 2, pp. 348\u2013374 (1980).","journal-title":"SIAM J. Comput."},{"issue":"8","key":"22_CR9","doi-asserted-by":"crossref","first-page":"1793","DOI":"10.1002\/j.1538-7305.1967.tb03172.x","volume":"46","author":"J. Hopcraft","year":"1967","unstructured":"Hopcraft, J. and Ullman, J., Unified theory of automata, The Bell System Technical J., Vol. 46, No. 8, pp. 1793\u20131829 (1967).","journal-title":"The Bell System Technical J."},{"issue":"2","key":"22_CR10","first-page":"88","volume":"5","author":"Q. Ibarra","year":"1971","unstructured":"Ibarra, Q., Characterizations of some tape and time complexity classes of Turing Machines in terms of multihead and auxiliary stack automata, JCSS, Vol. 5, No. 2, pp. 88\u2013117 (1971).","journal-title":"JCSS"},{"key":"22_CR11","first-page":"28","volume":"7","author":"O. Ibarra","year":"1973","unstructured":"Ibarra, O., On two-way multihead automata, JCSS, Vol. 7, pp. 28\u201336 (1973).","journal-title":"JCSS"},{"key":"22_CR12","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/S0019-9958(78)90570-3","volume":"37","author":"Y. Igarashi","year":"1978","unstructured":"Igarashi, Y., Tape bounds for some subclasses of deterministic context-free languages, Information and Control, Vol. 37, pp. 321\u2013333 (1978).","journal-title":"Information and Control"},{"issue":"3","key":"22_CR13","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/0206032","volume":"6","author":"Y. Igarashi","year":"1977","unstructured":"Igarashi, Y., The tape complexity of some classes of Szilard languages, SIAM J. Comput., Vol. 6, No. 3, pp. 461\u2013466 (1977).","journal-title":"SIAM J. Comput."},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Lewis, P., Hartmanis, J., and Stearns, R., Memory bounds for the recognition of context-free and context-sensitive languages, IEEE Conf. Record on Switching Circuit Theory and Logic Design, pp. 191\u2013202 (1965).","DOI":"10.1109\/FOCS.1965.14"},{"key":"22_CR15","unstructured":"Lipton, R. and Zalcstein, Y., Word problems solvable in logspace, Computer Science Department, Yale University, Tech. Report #6 (1976)."},{"issue":"4","key":"22_CR16","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N. Lynch","year":"1977","unstructured":"Lynch, N., Logspace recognition and translation of parenthesis languages, JACM, Vol. 24, No. 4, pp. 583\u2013590 (1977).","journal-title":"JACM"},{"issue":"6","key":"22_CR17","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(76)90013-2","volume":"5","author":"K. Mehlhorn","year":"1976","unstructured":"Mehlhorn, K., Bracket-languages are recognizable in logarithmic space, Information Processing Letters, Vol. 5, No. 6, pp. 168\u2013170 (1976).","journal-title":"Information Processing Letters"},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0019-9958(73)90237-4","volume":"22","author":"E. Moriya","year":"1973","unstructured":"Moriya, E., Associate languages and derivational complexity of formal grammars and languages, Information and Control, Vol. 22, pp. 139\u2013162 (1973).","journal-title":"Information and Control"},{"key":"22_CR19","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0019-9958(72)90205-7","volume":"20","author":"R. Richie","year":"1972","unstructured":"Richie, R. and Springsteel, F., Language recognition by marking automata, Information and Control, Vol. 20, pp. 313\u2013330 (1972).","journal-title":"Information and Control"},{"issue":"4","key":"22_CR20","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/321906.321913","volume":"22","author":"I. Sudborough","year":"1975","unstructured":"Sudborough, I., A note on tape-bounded complexity classes and linear context-free languages, JACM, Vol. 22, No. 4, pp. 499\u2013500 (1975).","journal-title":"JACM"},{"key":"22_CR21","first-page":"338","volume":"10","author":"I. Sudborough","year":"1979","unstructured":"Sudborough, I., On tape-bounded complexity classes and multihead finite automata, JCSS, 10, pp. 338\u2013345 (1979).","journal-title":"JCSS"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Sudborough, I., On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, 8th Annual ACM Symp. on Theory of Computing, pp. 141\u2013148 (1976).","DOI":"10.1145\/800113.803642"},{"key":"22_CR23","unstructured":"Valiant, L., Decision problems for families of deterministic pushdown automata, Ph.D. thesis, University of Warwick, U.K. (1973)."},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Verbeek, R., Time-space trade-offs for general recursion, Proc. 22nd IEEE-FOCS, pp. 228\u2013234 (1981).","DOI":"10.1109\/SFCS.1981.50"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-13345-3_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:07:14Z","timestamp":1605643634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-13345-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984]]},"ISBN":["9783540133452","9783540388869"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-13345-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1984]]}}}