{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T12:40:02Z","timestamp":1741437602216,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229923"},{"type":"electronic","value":"9783642229930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_38","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:44:46Z","timestamp":1312893886000},"page":"412-423","source":"Crossref","is-referenced-by-count":6,"title":["Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Krebs","sequence":"first","affiliation":[]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. SIAM Journal on Computing, 645\u2013655 (1999)","DOI":"10.1109\/SFFCS.1999.814641"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/237814.237823","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996","author":"N. Alon","year":"1996","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996, pp. 20\u201329. ACM, New York (1996), http:\/\/doi.acm.org\/10.1145\/237814.237823"},{"key":"38_CR3","unstructured":"Babu, A., Limaye, N., Radhakrishnan, J., Varma, G.: Streaming algorithms for language recognition problems. Tech. Rep. arXiv:1104.0848, Arxiv (2011)"},{"key":"38_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-642-13562-0_10","volume-title":"Theory and Applications of Models of Computation","author":"A. Babu","year":"2010","unstructured":"Babu, A., Limaye, N., Varma, G.: Streaming algorithms for some problems in log-space. In: Kratochv\u00edl, J., Li, A., Fiala, J., Kolman, P. (eds.) TAMC 2010. LNCS, vol.\u00a06108, pp. 94\u2013104. Springer, Heidelberg (2010), http:\/\/dx.doi.org\/10.1007\/978-3-642-13562-0_10 , doi:10.1007\/978-3-642-13562-0-10"},{"issue":"5","key":"38_CR5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0020-0190(89)90052-5","volume":"32","author":"D.A.M. Barrington","year":"1989","unstructured":"Barrington, D.A.M., Corbett, J.: On the relative complexity of some languages in NC 1. Information Processing Letters\u00a032(5), 251 (1989)","journal-title":"Information Processing Letters"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Cao, F., Ester, M., Qian, W., Zhou, A.: Density-based clustering over an evolving data stream with noise. In: 2006 SIAM Conference on Data Mining, pp. 328\u2013339 (2006)","DOI":"10.1137\/1.9781611972764.29"},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Cormode, G., Kondapally, R., McGregor, A.: Information cost tradeoffs for augmented index and streaming language recognition. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 387\u2013396 (2010)","DOI":"10.1109\/FOCS.2010.44"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Ganguly, S.: Data stream algorithms via expander graphs. In: Proceedings of the 19th International Symposium on Algorithms and Computation, pp. 52\u201363 (2008)","DOI":"10.1007\/978-3-540-92182-0_8"},{"issue":"4","key":"38_CR9","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.ipl.2006.01.014","volume":"99","author":"W. Huang","year":"2006","unstructured":"Huang, W., Shi, Y., Zhang, S., Zhu, Y.: The communication complexity of the hamming distance problem. Information Processing Letters\u00a099(4), 149\u2013153 (2006)","journal-title":"Information Processing Letters"},{"key":"38_CR10","unstructured":"Jain, R., Nayak, A.: The space complexity of recognizing well-parenthesized expressions. Tech. Rep. TR10-071, Electronic Colloquium on Computational Complexity (April 19, 2010) (revised July 5, 2010), http:\/\/eccc.hpi-web.de\/"},{"key":"38_CR11","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"2006","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (2006)"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"Magniez, F., Mathieu, C., Nayak, A.: Recognizing well-parenthesized expressions in the streaming model. In: STOC 2009 (2009)","DOI":"10.1145\/1806689.1806727"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science\u00a01(2) (2005)","DOI":"10.1561\/0400000002"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1145\/100216.100242","volume-title":"Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990","author":"N. Nisan","year":"1990","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computations. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 204\u2013212. ACM, New York (1990), http:\/\/doi.acm.org\/10.1145\/100216.100242"},{"key":"38_CR15","first-page":"261","volume-title":"Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science","author":"M. Parnas","year":"2001","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Testing parenthesis languages. In: Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 261\u2013272. Springer, Heidelberg (2001)"},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"Rudra, A., Uurtamo, S.: Data stream algorithms for codeword testing. In: ICALP (1), pp. 629\u2013640 (2010)","DOI":"10.1007\/978-3-642-14165-2_53"},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"Jayram, T.S, David, W.: Optimal bounds for johnson-lindenstrauss transforms and streaming problems with sub-constant error. In: SIAM: ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 (2011)","DOI":"10.1137\/1.9781611973082.1"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"Shaltiel, R.: Weak derandomization of weak algorithms: Explicit versions of yao\u2019s lemma. In: Annual IEEE Conference on Computational Complexity, pp. 114\u2013125 (2009)","DOI":"10.1109\/CCC.2009.27"},{"key":"38_CR19","unstructured":"Vadhan, S.: Pseudorandomness, monograph in preparation for FnTTCS (2010), http:\/\/people.seas.harvard.edu\/~salil\/pseudorandomness\/"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: On the power of quantum fingerprinting. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 77\u201381 (2003)","DOI":"10.1145\/780542.780554"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T12:06:58Z","timestamp":1741435618000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}