{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T19:16:42Z","timestamp":1672427802061},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,12,1]],"date-time":"1993-12-01T00:00:00Z","timestamp":754704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1993,12]]},"DOI":"10.1007\/bf01275490","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T08:08:55Z","timestamp":1111651735000},"page":"392-401","source":"Crossref","is-referenced-by-count":8,"title":["Two tapes versus one for off-line Turing machines"],"prefix":"10.1007","volume":"3","author":[{"given":"Wolfgang","family":"Maass","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Endre","family":"Szemer\ufffddi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\ufffdrgy","family":"Tur\ufffdn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0022-0000(88)90002-5","volume":"37","author":"N. Alon","year":"1988","unstructured":"N. Alon andW. Maass, Meanders and their application in lower bound arguments.J. Comput. System Sci. 37 (1988), 118?129.","journal-title":"J. Comput. System Sci."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0304-3975(90)90080-2","volume":"74","author":"L. Babai","year":"1990","unstructured":"L. Babai, P. Pudl\ufffdk, V. R\ufffddl, andE. Szemer\ufffddi, Lower bounds to the complexity of symmetric boolean functions.Theoret. Comput. Sci. 74 (1990), 313?323.","journal-title":"Theoret. Comput. Sci."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0020-0190(89)90160-9","volume":"33","author":"M. Dietzfelbinger","year":"1989","unstructured":"M. Dietzfelbinger, The speed of copying on one-tape off-line turing machines.Inform. Process. Lett. 33 (1989), 83?89.","journal-title":"Inform. Process. Lett."},{"key":"CR4","unstructured":"M. Dietzfelbinger and W. Maass, The complexity of matrix transposition on one-tape off-line turing machines with output tape, 1986. To appear inTheoret. Comput. Sci."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"P. Duris, Z. Galil, W. J. Paul, and R. Reischuk, Two nonlinear bounds. InProc. Fifteenth Ann. ACM Symp. Theor. Comput., 1983, 127?132.","DOI":"10.1145\/800061.808741"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F. C. Hennie","year":"1965","unstructured":"F. C. Hennie, One-tape off-line turing machine computations.Inform. and Control 8 (1965), 553?578.","journal-title":"Inform. and Control"},{"key":"CR7","unstructured":"J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0890-5401(88)90003-X","volume":"78","author":"M. Li","year":"1988","unstructured":"M. Li andP. M. B. Vitanyi, Tape versus quene and stacks: the lower bounds.Inform. and Comput. 78 (1988), 56?85.","journal-title":"Inform. and Comput."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/3-540-16486-3_101","volume":"223","author":"M. Li","year":"1986","unstructured":"M. Li, L. Longpre, andP. M. B. Vitanyi, The power of the queue.Proc. of Structure in Complexity Theory, Lecture Notes in Computer Science 223 (1986), 219?233.","journal-title":"Proc. of Structure in Complexity Theory, Lecture Notes in Computer Science"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton andR. E. Tarjan, A separator theorem for planar graphs.SIAM J. Appl. Math. 36 (1979), 177?189.","journal-title":"SIAM J. Appl. Math."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1090\/S0002-9947-1985-0808746-4","volume":"292","author":"W. Maass","year":"1985","unstructured":"W. Maass, Combinatorial lower bound arguments for deterministic and nondeterministic turing machines.Trans. Amer. Math. Soc. 292 (1985), 675?693.","journal-title":"Trans. Amer. Math. Soc."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/3-540-16486-3_103","volume":"223","author":"W. Maass","year":"1986","unstructured":"W. Maass andG. Schnitger, An optimal lower bound for turing machines with one work tape and a two-way input tape.Proc. of Structure in Complexity Theory, Lecture Notes in Computer Science 223 (1986), 249?264.","journal-title":"Proc. of Structure in Complexity Theory, Lecture Notes in Computer Science"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"W. Maass, G. Schnitger, and E.Szemer\ufffddi, Two tapes are better than one for off-line turing machines. InProc. Nineteenth Ann. ACM Symp. Theor. Comput., 1987, 94?100.","DOI":"10.1145\/28395.28406"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"W. J. Paul, N. Pippenger, E. Szemer\ufffddi, and W. Trotter, On determinism versus nondeterminism and related problems. InProc. 24th Ann. Symp. Found. Comput. Sci., 1983, 429?438.","DOI":"10.1109\/SFCS.1983.39"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF02759719","volume":"1","author":"M. O. Rabin","year":"1963","unstructured":"M. O. Rabin, Real time computation.Israel J. of Math. 1 (1963), 203?211.","journal-title":"Israel J. of Math."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0022-0000(84)90033-3","volume":"29","author":"J.E. Savage","year":"1984","unstructured":"J.E. Savage, The performance of multilective vlsi algorithms.J. Comput. System Sci. 29 (1984), 243?272.","journal-title":"J. Comput. System Sci."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01275490.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01275490\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01275490","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:02:36Z","timestamp":1586178156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01275490"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["BF01275490"],"URL":"https:\/\/doi.org\/10.1007\/bf01275490","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}