{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T02:01:24Z","timestamp":1726452084514},"reference-count":16,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[1985,1,1]],"date-time":"1985-01-01T00:00:00Z","timestamp":473385600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":10424,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1985]]},"DOI":"10.1016\/0304-3975(85)90132-x","type":"journal-article","created":{"date-parts":[[2003,5,13]],"date-time":"2003-05-13T04:04:58Z","timestamp":1052798698000},"page":"89-106","source":"Crossref","is-referenced-by-count":4,"special_numbering":"C","title":["On efficient recognition of transductions and relations"],"prefix":"10.1016","volume":"39","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Palis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jik H.","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/0304-3975(85)90132-X_BIB1","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(68)91087-5","article-title":"Time and tape complexity of pushdown automata","volume":"13","author":"Aho","year":"1968","journal-title":"Information and Control"},{"year":"1974","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","key":"10.1016\/0304-3975(85)90132-X_BIB2"},{"issue":"194","key":"10.1016\/0304-3975(85)90132-X_BIB3","first-page":"487","article-title":"On economical construction of the transitive closure of a directed graph","volume":"1","author":"Arlazarov","year":"1970","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"10.1016\/0304-3975(85)90132-X_BIB4","series-title":"Proc. IFIP Congress","article-title":"Linear time simulation of deterministic two-way pushdown automata","author":"Cook","year":"1972"},{"key":"10.1016\/0304-3975(85)90132-X_BIB5","series-title":"Proc. 8th Ann. ACM Symp. of Theory of Computing","first-page":"112","article-title":"On line context free language recognition in less than cubic time","author":"Graham","year":"1976"},{"key":"10.1016\/0304-3975(85)90132-X_BIB6","first-page":"5","article-title":"A note on the recognition of one-counter languages","volume":"9","author":"Greibach","year":"1975","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/0304-3975(85)90132-X_BIB7","series-title":"Proc. 16th Ann. Symp. on Foundations of Computer Science","first-page":"57","article-title":"On time versus space and related problems","author":"Hopcroft","year":"1975"},{"key":"10.1016\/0304-3975(85)90132-X_BIB8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(71)80029-6","article-title":"Characterizations of some tapes and 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\/0304-3975(85)90132-X_BIB9","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/S0022-0000(73)80048-0","article-title":"On two-way multihead automata","volume":"7","author":"Ibarra","year":"1973","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(85)90132-X_BIB10","series-title":"Lecture Notes in Computer Science (11th Colloquium on Automata, Languages and Programming)","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-13345-3_22","article-title":"Space and time efficient simulations and characterizations of some restricted classes of PDA's","author":"Ibarra","year":"1984"},{"issue":"4, 5","key":"10.1016\/0304-3975(85)90132-X_BIB11","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/0020-0190(81)90044-2","article-title":"Time complexity of languages recognized by one-way multihead pushdown automata","volume":"13","author":"Rytter","year":"1981","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"10.1016\/0304-3975(85)90132-X_BIB12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(82)90075-8","article-title":"A note on two-way nondeterministic pushdown automata","volume":"15","author":"Rytter","year":"1982","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(85)90132-X_BIB13","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","article-title":"Note on halting space-bounded computation","volume":"10","author":"Sipser","year":"1980","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10.1016\/0304-3975(85)90132-X_BIB14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1051\/ita\/1977110301811","article-title":"Some remarks on multihead finite automata","volume":"11","author":"Sudborough","year":"1977","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/0304-3975(85)90132-X_BIB15","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","article-title":"General context-free recognition in less than cubic time","volume":"10","author":"Valiant","year":"1975","journal-title":"Comput. System Sci."},{"issue":"1","key":"10.1016\/0304-3975(85)90132-X_BIB16","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0020-0190(82)90138-7","article-title":"Efficient recognition of rational relations","volume":"14","author":"van Leeuwen","year":"1982","journal-title":"Inform. Process. Lett."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439758590132X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439758590132X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T12:52:55Z","timestamp":1553172775000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439758590132X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985]]},"references-count":16,"alternative-id":["030439758590132X"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(85)90132-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[1985]]}}}