{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:58Z","timestamp":1759638178939},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424949"},{"type":"electronic","value":"9783540446798"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44679-6_24","type":"book-chapter","created":{"date-parts":[[2010,2,9]],"date-time":"2010-02-09T17:00:37Z","timestamp":1265734837000},"page":"218-227","source":"Crossref","is-referenced-by-count":1,"title":["Stacks versus Deques"],"prefix":"10.1007","author":[{"given":"Holger","family":"Petersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,31]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(85)90164-1","volume":"40","author":"K. Ayers","year":"1985","unstructured":"Kathleen Ayers Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages. Theoretical Computer Science, 40:163\u2013174, 1985.","journal-title":"Theoretical Computer Science"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R. V. Book","year":"1970","unstructured":"Ronald V. Book and Sheila A. Greibach Quasi-realtime languages. Mathematical Systems Theory, 4:97\u2013111, 1970.","journal-title":"Mathematical Systems Theory"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/0304-3975(87)90115-0","volume":"52","author":"F. J. Brandenburg","year":"1987","unstructured":"Franz J. Brandenburg A note on:\u2019 Deque automata and a subfamily of contextsensitive languages which contains all semilinear bounded languages\u2019 (by K. Ayers). Theoretical Computer Science, 52:341\u2013342, 1987.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Tyng-Ruey Chuang and Benjamin Goldberg Real-time deques, multihead Turing machines, and purely functional programming. In Conference on Functional Programming Languages and Computer Architecture, pages 289\u2013298, 1993.","key":"24_CR4","DOI":"10.1145\/165180.165225"},{"key":"24_CR5","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1145\/321724.321726","volume":"19","author":"P. C. Fischer","year":"1972","unstructured":"Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg Real-time simulation of multihead tape units. Journal of the Association for Computing Machinery, 19:590\u2013607, 1972.","journal-title":"Journal of the Association for Computing Machinery"},{"doi-asserted-by":"crossref","unstructured":"Zvi Galil, Ravi Kannan, and Endre Szemeredi On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines. In Proceedings of the 18th ACM Symposium on Theory of Computing (STOC), Berkeley, California, pages 39\u201349, 1986.","key":"24_CR6","DOI":"10.1145\/12130.12135"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2307\/1994208","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Juris Hartmanis and Richard E. Stearns On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285\u2013306, 1965.","journal-title":"Transactions of the American Mathematical Society"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/0020-0190(81)90030-2","volume":"13","author":"R. Hood","year":"1981","unstructured":"Robert Hood and Robert Melville Real time queue operations in pure Lisp. Information Processing Letters, 13:50\u201354, 1981.","journal-title":"Information Processing Letters"},{"key":"24_CR9","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/256303.256308","volume":"44","author":"T. Jiang","year":"1997","unstructured":"Tao Jiang, Joel I. Seiferas, and Paul M. B. Vit#x00E1;nyi Two heads are better than two tapes. Journal of the Association for Computing Machinery, 44:237\u2013256, 1997.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"24_CR10","volume-title":"The Art of Computer Programming","author":"D. E. Knuth","year":"1997","unstructured":"Donald E. Knuth The Art of Computer Programming, volume 1. Addison-Wesley, Reading Mass., 3rd edition, 1997.","edition":"3rd edition"},{"key":"24_CR11","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1145\/322234.322246","volume":"28","author":"B. L. Leong","year":"1981","unstructured":"Benton L. Leong and Joel I. Seiferas New real-time simulations of multihead tape units. Journal of the Association for Computing Machinery, 28:166\u2013180, 1981.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0022-0000(88)90047-5","volume":"37","author":"M. Li","year":"1988","unstructured":"Ming Li Simulating two pushdown stores by one tape in O(n1.5vlog n) time. Journal of Computer and System Sciences, 37:101\u2013116, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/0221042","volume":"21","author":"M. Li","year":"1992","unstructured":"Ming Li, Luc Longpr\u00e9, and Paul Vit\u00e1nyi The power of the queue. SIAM Journal on Computing, 21:697\u2013712, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"24_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1993","unstructured":"Ming Li and Paul Vit\u00e1nyi An Introduction to Kolmogorov Complexity and its Applications. Springer, Berlin-Heidelberg-New York, 1993."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0890-5401(88)90003-X","volume":"78","author":"M. Li","year":"1988","unstructured":"Ming Li and Paul M. B. Vit\u00e1nyi Tape versus queue and stacks: The lower bounds. Information and Computation, 78:56\u201385, 1988.","journal-title":"Information and Computation"},{"key":"24_CR16","first-page":"3","volume":"1","author":"B. Rosenberg","year":"1993","unstructured":"Burton Rosenberg Simulating a stack by queues. In Proceedings of the XIX Latinamerican Conference on Computer Science, volume 1, pages 3\u201313, 1993.","journal-title":"Proceedings of the XIX Latinamerican Conference on Computer Science"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF02238815","volume":"6","author":"H.-J. Sto\u00df","year":"1970","unstructured":"Hanns-J\u00f6rg Sto\u00df k-Band Simulation von k-Kopf Turingmaschinen. (k-tape simulation of k-head Turing machines). Computing, 6:309\u2013317, 1970. In German.","journal-title":"Computing"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44679-6_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T21:32:42Z","timestamp":1558819962000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44679-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424949","9783540446798"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44679-6_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}