{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T04:58:23Z","timestamp":1648616303572},"reference-count":20,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1985,10,1]],"date-time":"1985-10-01T00:00:00Z","timestamp":496972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,18]],"date-time":"2013-07-18T00:00:00Z","timestamp":1374105600000},"content-version":"vor","delay-in-days":10152,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Control"],"published-print":{"date-parts":[[1985,10]]},"DOI":"10.1016\/s0019-9958(85)80030-9","type":"journal-article","created":{"date-parts":[[2005,5,3]],"date-time":"2005-05-03T11:12:14Z","timestamp":1115118734000},"page":"126-143","source":"Crossref","is-referenced-by-count":0,"title":["On space and time efficient TM simulations of some restricted classes of PDA's"],"prefix":"10.1016","volume":"67","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":"78","reference":[{"key":"10.1016\/S0019-9958(85)80030-9_bib1","series-title":"Proc. 11th ACM Sympos. on Theory of Comput.","first-page":"338","article-title":"Deterministic CFL's are accepted simultaneously in polynomial time and log squared space","author":"Cook","year":"1979"},{"key":"10.1016\/S0019-9958(85)80030-9_bib2","series-title":"Proc. 1971 Internat. Fed. Inform. Process Congress","first-page":"75","article-title":"Linear time simulation of deterministic two-way pushdown automata","author":"Cook","year":"1971"},{"issue":"No. 3","key":"10.1016\/S0019-9958(85)80030-9_bib3","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01694011","article-title":"Counter machines and counter languages","volume":"2","author":"Fischer","year":"1968","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0019-9958(85)80030-9_bib4","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF01683273","article-title":"Two-way deterministic pushdown automaton languages and some open problems in the theory of computing","volume":"10","author":"Galil","year":"1977","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0019-9958(85)80030-9_bib5","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"issue":"No. 2","key":"10.1016\/S0019-9958(85)80030-9_bib6","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(71)80029-6","article-title":"Characterizations of some tape and time complexity classes of Turing Machines in terms of multihead and auxiliary stack automata","volume":"5","author":"Ibarra","year":"1971","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0019-9958(85)80030-9_bib7","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/S0019-9958(78)90570-3","article-title":"Tape bounds for some subclasses of deterministic context-free languages","volume":"37","author":"Igarashi","year":"1978","journal-title":"Inform. Contr."},{"issue":"No. 3","key":"10.1016\/S0019-9958(85)80030-9_bib8","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/0206032","article-title":"The tape complexity of some classes of Szilard languages","volume":"6","author":"Igarashi","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0019-9958(85)80030-9_bib9","series-title":"IEEE Conf. Record on Switching Circuit Theory and Logic Design","first-page":"191","article-title":"Memory bounds for the recognition of context-free and context-sensitive languages","author":"Lewis","year":"1965"},{"key":"10.1016\/S0019-9958(85)80030-9_bib10","article-title":"Word Problems Solvable in Logspace","author":"Lipton","year":"1976"},{"issue":"No. 4","key":"10.1016\/S0019-9958(85)80030-9_bib11","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/322033.322037","article-title":"Logspace recognition and translation of parenthesis languages","volume":"24","author":"Lynch","year":"1977","journal-title":"J. Assoc. Comput. Mach."},{"issue":"No. 6","key":"10.1016\/S0019-9958(85)80030-9_bib12","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(76)90013-2","article-title":"Bracket-languages are recognizable in logarithmic space","volume":"5","author":"Mehlhorn","year":"1976","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0019-9958(85)80030-9_bib13","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0019-9958(73)90237-4","article-title":"Associate languages and derivational complexity of formal grammars and languages","volume":"22","author":"Moriya","year":"1973","journal-title":"Inform. Contr."},{"key":"10.1016\/S0019-9958(85)80030-9_bib14","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0019-9958(72)90205-7","article-title":"Language recognition by marking automata","volume":"20","author":"Richie","year":"1972","journal-title":"Inform. Contr."},{"issue":"No. 4","key":"10.1016\/S0019-9958(85)80030-9_bib15","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/321906.321913","article-title":"A note on tape-bounded complexity classes and linear context-free languages","volume":"22","author":"Sudborough","year":"1975","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0019-9958(85)80030-9_bib16","article-title":"Decision Problems for Families of Deterministic Pushdown Automata","author":"Valiant","year":"1973"},{"key":"10.1016\/S0019-9958(85)80030-9_bib17","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(74)90839-0","article-title":"The equivalence problem for deterministic finite-turn pushdown automata","volume":"25","author":"Valiant","year":"1974","journal-title":"Inform. Contr."},{"key":"10.1016\/S0019-9958(85)80030-9_bib18","series-title":"Proc. 22nd IEEE Found. of Comput. Sci.","first-page":"228","article-title":"Time-space trade-offs for general recursion","author":"Verbeek","year":"1981"},{"key":"10.1016\/S0019-9958(85)80030-9_bib19","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/S0019-9958(83)80049-7","article-title":"The recognition of deterministic CFL's in small time and space","volume":"56","author":"von Braum\u00fchl","year":"1983","journal-title":"Inform. Contr."},{"key":"10.1016\/S0019-9958(85)80030-9_bib20","series-title":"Proc. 21st IEEE Found of Comput. Sci.","first-page":"411","article-title":"A recognition algorithm for deterministic CFLs optimal in time and space","author":"von Braum\u00fchl","year":"1980"}],"container-title":["Information and Control"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0019995885800309?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0019995885800309?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,26]],"date-time":"2019-01-26T19:55:39Z","timestamp":1548532539000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0019995885800309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,10]]},"references-count":20,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1985,10]]}},"alternative-id":["S0019995885800309"],"URL":"https:\/\/doi.org\/10.1016\/s0019-9958(85)80030-9","relation":{},"ISSN":["0019-9958"],"issn-type":[{"value":"0019-9958","type":"print"}],"subject":[],"published":{"date-parts":[[1985,10]]}}}