{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T18:46:28Z","timestamp":1767033988562,"version":"3.37.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319773124"},{"type":"electronic","value":"9783319773131"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77313-1_2","type":"book-chapter","created":{"date-parts":[[2018,3,7]],"date-time":"2018-03-07T02:20:49Z","timestamp":1520389249000},"page":"26-35","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Sliding Window Algorithms for Regular Languages"],"prefix":"10.1007","author":[{"given":"Moses","family":"Ganardi","sequence":"first","affiliation":[]},{"given":"Danny","family":"Hucke","sequence":"additional","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,8]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-47534-9","volume-title":"Data Streams - Models and Algorithms","author":"CC Aggarwal","year":"2007","unstructured":"Aggarwal, C.C.: Data Streams - Models and Algorithms. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-0-387-47534-9"},{"issue":"1","key":"2_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.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows. In: Proceedings of PODS 2004, pp. 286\u2013296. ACM (2004)","DOI":"10.1145\/1055558.1055598"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Babcock, B., Datar, M., Motwani, R., O\u2019Callaghan, L.: Maintaining variance and k-medians over data stream windows. In: Proceedings of PODS 2003, pp. 234\u2013243. ACM (2003)","DOI":"10.1145\/773153.773176"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2012.12.028","volume":"494","author":"A Babu","year":"2013","unstructured":"Babu, A., Limaye, N., Radhakrishnan, J., Varma, G.: Streaming algorithms for language recognition problems. Theor. Comput. Sci. 494, 13\u201323 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR6","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. 6108, pp. 94\u2013104. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13562-0_10"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"2006","DOI":"10.1007\/978-1-4939-2864-4","volume-title":"Encyclopedia of Algorithms","author":"V Braverman","year":"2016","unstructured":"Braverman, V.: Sliding window algorithms. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 2006\u20132011. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R.: Smooth histograms for sliding windows. In: Proceedings of FOCS 2007, pp. 283\u2013293. IEEE Computer Society (2007)","DOI":"10.1109\/FOCS.2007.55"},{"issue":"1","key":"2_CR9","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.jcss.2011.04.004","volume":"78","author":"V Braverman","year":"2012","unstructured":"Braverman, V., Ostrovsky, R., Zaniolo, C.: Optimal sampling from sliding windows. J. Comput. Syst. Sci. 78(1), 260\u2013272 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Breslauer, D., Galil, Z.: Real-time streaming string-matching. ACM Trans. Algorithms 10(4), 22:1\u201322:12 (2014)","DOI":"10.1145\/2635814"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-662-48350-3_31","volume-title":"Algorithms \u2013 ESA 2015","author":"R Clifford","year":"2015","unstructured":"Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.: Dictionary matching in a stream. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 361\u2013372. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_31"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.: The k-mismatch problem revisited. In: Proceedings of SODA 2016, pp. 2039\u20132052. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch142"},{"key":"2_CR13","unstructured":"Clifford, R., Starikovskaya, T.: Approximate hamming distance in a stream. In: Proceedings of ICALP 2016. LIPIcs, vol. 55, pp. 20:1\u201320:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-642-40450-4_29","volume-title":"Algorithms \u2013 ESA 2013","author":"MS Crouch","year":"2013","unstructured":"Crouch, M.S., McGregor, A., Stubbs, D.: Dynamic graphs in the sliding-window model. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 337\u2013348. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_29"},{"issue":"6","key":"2_CR15","doi-asserted-by":"crossref","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM J. Comput. 31(6), 1794\u20131813 (2002)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2_CR16","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P Flajolet","year":"1985","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31(2), 182\u2013209 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR17","unstructured":"Fran\u00e7ois, N., Magniez, F., de Rougemont, M., Serre, O.: Streaming property testing of visibly pushdown languages. In: Proceedings of ESA 2016. LIPIcs, vol. 57, pp. 43:1\u201343:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"2_CR18","unstructured":"Ganardi, M., Hucke, D., K\u00f6nig, D., Lohrey, M., Mamouras, K.: Automata theory on sliding windows. In: Proceedings of STACS 2018. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018, to appear)"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Querying regular languages over sliding windows. In: Proceedings of FSTTCS 2016. LIPIcs, vol. 65, pp. 18:1\u201318:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)","DOI":"10.1007\/s00224-020-10000-1"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Golab, L., \u00d6zsu, M.T.: Processing sliding window multi-joins in continuous queries over data streams. In: Proceedings of VLDB 2003, pp. 500\u2013511. Morgan Kaufmann (2003)","DOI":"10.1016\/B978-012722442-8\/50051-3"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-642-22993-0_38","volume-title":"Mathematical Foundations of Computer Science 2011","author":"A Krebs","year":"2011","unstructured":"Krebs, A., Limaye, N., Srinivasan, S.: Streaming algorithms for recognizing nearly well-parenthesized expressions. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 412\u2013423. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22993-0_38"},{"issue":"6","key":"2_CR22","doi-asserted-by":"crossref","first-page":"1880","DOI":"10.1137\/130926122","volume":"43","author":"F Magniez","year":"2014","unstructured":"Magniez, F., Mathieu, C., Nayak, A.: Recognizing well-parenthesized expressions in the streaming model. SIAM J. Comput. 43(6), 1880\u20131905 (2014)","journal-title":"SIAM J. Comput."},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Lewis II, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, pp. 191\u2013202. IEEE Computer Society (1965)","DOI":"10.1109\/FOCS.1965.14"},{"key":"2_CR24","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.: Selection and sorting with limited storage. Theor. Comput. Sci. 12, 315\u2013323 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/11965893_21","volume-title":"Database Theory \u2013 ICDT 2007","author":"L Segoufin","year":"2006","unstructured":"Segoufin, L., Sirangelo, C.: Constant-memory validation of streaming XML documents against DTDs. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol. 4353, pp. 299\u2013313. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11965893_21"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Segoufin, L., Vianu, V.: Validating streaming XML documents. In: Proceedings of PODS 2002, pp. 53\u201364. ACM (2002)","DOI":"10.1145\/543613.543622"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Stearns, R.E., Hartmanis, J., Lewis II, P.M.: Hierarchies of memory limited computations. In: Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, pp. 179\u2013190. IEEE Computer Society (1965)","DOI":"10.1109\/FOCS.1965.11"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77313-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T12:51:22Z","timestamp":1660567882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-77313-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319773124","9783319773131"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77313-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}