{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T11:11:37Z","timestamp":1648984297464},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p>If the machines of some type A have enough resources to (i) solve problems that no machine of type B can solve, and (ii) simulate any unary two-way deterministic finite automaton that has access to a linearly-bounded counter, then typically no recursive function can upper bound the increase in the size of description when a machine of type A is replaced by an equivalent machine of type B.<\/jats:p>","DOI":"10.1142\/s012905410500339x","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T11:41:41Z","timestamp":1129203701000},"page":"943-956","source":"Crossref","is-referenced-by-count":1,"title":["NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES"],"prefix":"10.1142","volume":"16","author":[{"given":"CHRISTOS","family":"KAPOUTSIS","sequence":"first","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90087-1"},{"key":"rf2","first-page":"265","volume":"3","author":"Fischer M. J.","journal-title":"Mathematical Syst. Theory"},{"key":"rf3","first-page":"193","volume":"8","author":"Goldstine J.","journal-title":"J. UCS"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/0209010"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90016-6"},{"key":"rf6","first-page":"117","volume":"37","author":"Hartmanis J.","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"rf8","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft J. E.","year":"1979"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80048-0"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"rf15","volume-title":"Computation: finite and infinite machines","author":"Minsky M. L.","year":"1967"},{"key":"rf16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF00263746","volume":"6","author":"Monien B.","journal-title":"Acta Inform."},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/BF00271346"},{"key":"rf18","first-page":"67","volume":"14","author":"Monien B.","journal-title":"Theor. Inform. Appl."},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1137\/0206039"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80042-1"},{"key":"rf22","first-page":"323","volume":"11","author":"Stearns R. E.","journal-title":"Inform. and Comput."},{"key":"rf23","first-page":"139","volume":"32","author":"Valiant L. G.","journal-title":"Inform. and Comput."},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1145\/320856.320867"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905410500339X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T08:14:30Z","timestamp":1586506470000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410500339X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":19,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S012905410500339X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410500339x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}