{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T03:27:57Z","timestamp":1725593277406},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642214578"},{"type":"electronic","value":"9783642214585"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_17","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T17:11:27Z","timestamp":1309194687000},"page":"184-196","source":"Crossref","is-referenced-by-count":1,"title":["Space Lower Bounds for Online Pattern Matching"],"prefix":"10.1007","author":[{"given":"Rapha\u00ebl","family":"Clifford","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Jalsenius","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Sach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1006\/jagm.2000.1120","volume":"37","author":"A. Amir","year":"2000","unstructured":"Amir, A., Aumann, Y., Landau, G., Lewenstein, M., Lewenstein, N.: Pattern Matching with Swaps. Journal of Algorithms\u00a037, 247\u2013266 (2000)","journal-title":"Journal of Algorithms"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: Approximating edit distance efficiently. In: FOCS 2004: Proc. 45th Annual Symp. Foundations of Computer Science, pp. 550\u2013559 (2004)","DOI":"10.1109\/FOCS.2004.14"},{"issue":"2","key":"17_CR3","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0217015","volume":"17","author":"B. Chor","year":"1988","unstructured":"Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing\u00a017(2), 230\u2013261 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"17_CR4","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M. Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Inkyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM Journal on computing\u00a031(6), 1794\u20131813 (2002)","journal-title":"SIAM Journal on computing"},{"issue":"4","key":"17_CR5","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"},{"issue":"1","key":"17_CR6","doi-asserted-by":"publisher","first-page":"129","DOI":"10.4086\/toc.2008.v004a006","volume":"4","author":"T.S. Jayram","year":"2008","unstructured":"Jayram, T.S., Kumar, R., Sivakumar, D.: The one-way communication complexity of hamming distance. Theory of Computing\u00a04(1), 129\u2013135 (2008)","journal-title":"Theory of Computing"},{"key":"17_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"3","key":"17_CR8","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.jcss.2008.08.005","volume":"75","author":"C. Linhart","year":"2009","unstructured":"Linhart, C., Shamir, R.: Faster pattern matching with character classes using prime number encoding. Journal of Computer and System Sciences\u00a075(3), 155\u2013162 (2009)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"17_CR9","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1006\/inco.1995.1144","volume":"122","author":"S. Muthukrishnan","year":"1995","unstructured":"Muthukrishnan, S., Ramesh, H.: String matching under a general matching relation. Inf. Comput.\u00a0122(1), 140\u2013148 (1995)","journal-title":"Inf. Comput."},{"issue":"2","key":"17_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Information Processing Letters\u00a039(2), 67\u201371 (1991)","journal-title":"Information Processing Letters"},{"key":"17_CR11","unstructured":"Nisan, N.: Personal communication (2011)"},{"key":"17_CR12","unstructured":"P\u01cetra\u015fcu, M.: CC4: One-Way Communication and a Puzzle, 2009 (accessed January 20, 2011), http:\/\/infoweekly.blogspot.com\/2009\/04\/cc4-one-way-communication-and-puzzle.html"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: FOCS 2009: Proc. 50th Annual Symp. Foundations of Computer Science, pp. 315\u2013323 (2009)","DOI":"10.1109\/FOCS.2009.11"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Some complexity questions related to distributive computing. In: STOC 1979: Proc. 11th Annual ACM Symp. Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T08:04:48Z","timestamp":1560326688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}