{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:50Z","timestamp":1740109490682,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,1,8]],"date-time":"2013-01-08T00:00:00Z","timestamp":1357603200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00037-012-0057-1","type":"journal-article","created":{"date-parts":[[2013,1,7]],"date-time":"2013-01-07T08:18:04Z","timestamp":1357546684000},"page":"99-146","source":"Crossref","is-referenced-by-count":0,"title":["Tradeoff lower lounds for stack machines"],"prefix":"10.1007","volume":"23","author":[{"given":"Matei","family":"David","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Periklis A.","family":"Papakonstantinou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,1,8]]},"reference":[{"issue":"4","key":"57_CR1","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1145\/76359.76370","volume":"36","author":"E.W Allender","year":"1989","unstructured":"Allender E.W (1989) P-uniform circuit complexity. J. Assoc. Comput. Mach. 36(4): 912\u2013928 ISSN 0004-5411","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"57_CR2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon N., Matias Y., Szegedy M (1999) The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137\u2013147","journal-title":"Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"S. Arora & B. Barak (2009) Computational Complexity: A Modern Approach. Cambridge University Press.","key":"57_CR3","DOI":"10.1017\/CBO9780511804090"},{"issue":"2","key":"57_CR4","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"Babai L., Nisan N., Szegedy M. (1992) Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci. 45(2): 204\u2013232 ISSN 0022-0000","journal-title":"Syst. Sci."},{"unstructured":"P. Beame & D.-T. Huynh-Ngoc (2008). On the Value of Multiple Read\/Write Streams for Approximating Frequency Moments. In FOCS, 499\u2013508. IEEE. ISBN 978-0-7695-3436-7.","key":"57_CR5"},{"doi-asserted-by":"crossref","unstructured":"P. Beame , T. S. Jayram & A. Rudra (2007). Lower bounds for randomized read\/write stream algorithms. In STOC , 689\u2013698. ACM.","key":"57_CR6","DOI":"10.1145\/1250790.1250891"},{"doi-asserted-by":"crossref","unstructured":"R. V. Book (1974). Tally Languages and Complexity Classes. Information and Control 26 (2), 186\u2013193.","key":"57_CR7","DOI":"10.1016\/S0019-9958(74)90473-2"},{"doi-asserted-by":"crossref","unstructured":"A. Borodin , S. A. Cook , P. Dymond , L. Ruzzo & M. Tompa (1989). Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18.","key":"57_CR8","DOI":"10.1137\/0218038"},{"doi-asserted-by":"crossref","unstructured":"F.-J. Brandenburg (1977). On one-way auxiliary pushdown automata. In Theoretical Computer Science, 3rd GI -Conference, Darmstadt, Germany, March 28-30, 1977, Proceedings, H. Tzschach , H. Waldschmidt & Hermann K.-G. Walter , editors, volume 48 of Lecture Notes in Computer Science, 132\u2013144. Springer. ISBN 3-540-08138-0. http:\/\/dx.doi.org\/10.1007\/3-540-08138-0_11 .","key":"57_CR9","DOI":"10.1007\/3-540-08138-0_11"},{"issue":"4","key":"57_CR10","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1137\/0220039","volume":"20","author":"Jian-er Chen","year":"1991","unstructured":"Jian-er Chen M., Jian-er Chen M. (1991) Reversal complexity. SIAM J. Comput. 20(4): 622\u2013638 ISSN 0097-5397","journal-title":"SIAM J. Comput."},{"issue":"2","key":"57_CR11","first-page":"230","volume":"17","author":"B. Chor","year":"1988","unstructured":"Chor B., Goldreich O. (1988) Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. Comput. 17(2): 230\u2013261","journal-title":"Comput."},{"key":"57_CR12","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S.A Cook","year":"1971","unstructured":"Cook S.A (1971) Characterizations of pushdown machines in terms of time-bounded computers. J. Assoc. Comput. Mach. 18: 4\u201318 ISSN 0004-5411","journal-title":"Comput. Mach."},{"unstructured":"P. Erd\u00f6s & G. Szekeres (1935). A combinatorial problem in geometry. Compositio Math. 2: 463-470.","key":"57_CR13"},{"doi-asserted-by":"crossref","unstructured":"M. Grohe , A. Hernich & N. Schweikardt (2006). Randomized computations on large data sets: Tight lower bounds. In PODS, 243\u2013252. ACM.","key":"57_CR14","DOI":"10.1145\/1142351.1142387"},{"unstructured":"M. Grohe & N. Schweikardt (2005). Lower bounds for sorting with few random accesses to external memory. In PODS , 238\u2013249. ACM. ISBN 1-59593-062-0.","key":"57_CR15"},{"unstructured":"A. Gronemeier (2009). Asymptotically Optimal Lower Bounds on the NIH -Multi-Party Information Complexity of the AND -Function and Disjointness. In STACS, 505\u2013516.","key":"57_CR16"},{"unstructured":"A. Hernich & N. Schweikardt (2008). Reversal complexity revisited. Theor. Comput. Sci. 401 (1-3), 191\u2013205. ISSN 0304-3975.","key":"57_CR17"},{"doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity. Cambridge University Press, New York, NY, USA. ISBN 0-521-56067-5.","key":"57_CR18","DOI":"10.1016\/S0065-2458(08)60342-3"},{"issue":"2","key":"57_CR19","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W.L Ruzzo","year":"1980","unstructured":"Ruzzo W.L (1980) Tree-Size Bounded Alternation. J. Comput. Syst. Sci. 21(2): 218\u2013235","journal-title":"Syst. Sci."},{"issue":"3","key":"57_CR20","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W.L Ruzzo","year":"1981","unstructured":"Ruzzo W.L (1981) On Uniform Circuit Complexity. J. Comput. Syst. Sci. 22(3): 365\u2013383","journal-title":"Syst. Sci."},{"unstructured":"M. Sipser (1997). Introduction to the Theory of Computation. PWS Publishing Company.","key":"57_CR21"},{"issue":"2","key":"57_CR22","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"43","author":"H. Venkateswaran","year":"1991","unstructured":"Venkateswaran H. (1991) Properties that characterize LOGCFL. J. Comput. System Sci. 43(2): 380\u2013404 ISSN 0022-0000","journal-title":"System Sci."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0057-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0057-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0057-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,7]],"date-time":"2019-07-07T21:51:45Z","timestamp":1562536305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0057-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,8]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["57"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0057-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2013,1,8]]}}}