{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:45:24Z","timestamp":1794339924651,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540341666","type":"print"},{"value":"9783540341680","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11753728_15","type":"book-chapter","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T16:17:13Z","timestamp":1146154633000},"page":"127-136","source":"Crossref","is-referenced-by-count":11,"title":["Window Subsequence Problems for Compressed Texts"],"prefix":"10.1007","author":[{"given":"Patrick","family":"C\u00e9gielski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ir\u00e8ne","family":"Guessarian","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yury","family":"Lifshits","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Matiyasevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"15_CR1","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/jcss.1996.0023","volume":"52","author":"A. Amir","year":"1996","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern matching in Z\u2013compressed files. J. Comput. Syst. Sci.\u00a052(2), 299\u2013307 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"15_CR2","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P. Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L., Plandowski, W., Rytter, W.: On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. Journal of Computer and Systems Science\u00a065(2), 332\u2013350 (2002)","journal-title":"Journal of Computer and Systems Science"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/BFb0017130","volume-title":"Mathematical Foundations of Computer Science 1988","author":"M. Crochemore","year":"1988","unstructured":"Crochemore, M.: String-matching with constraints. In: Koubek, V., Janiga, L., Chytil, M.P. (eds.) MFCS 1988. LNCS, vol.\u00a0324, pp. 44\u201358. Springer, Heidelberg (1988)"},{"key":"15_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-61422-2_148","volume-title":"Algorithm Theory - SWAT \u201996","author":"L. Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient Algorithms for Lempel-Ziv Encoding (Extended Abstract). In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/3-540-45995-2_31","volume-title":"LATIN 2002: Theoretical Informatics","author":"B. Genest","year":"2002","unstructured":"Genest, B., Muscholl, A.: Pattern Matching and Membership for Hierarchical Message Sequence Charts. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 326\u2013340. Springer, Heidelberg (2002)"},{"issue":"3","key":"15_CR6","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"G. Ziv","year":"1977","unstructured":"Ziv, G., Lempel, A.: A universal algorithm for sequential data compresssion. IEEE Transactions on Information Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Transactions on Information Theory"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"G. Ziv","year":"1978","unstructured":"Ziv, G., Lempel, A.: Compresssion of individual sequences via variable-rate coding. IEEE Transactions on Information Theory\u00a024, 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"},{"key":"15_CR8","unstructured":"Lifshits, Y.: On the computational complexity of embedding of compressed texts, St.Petersburg State University Diploma thesis, (2005), http:\/\/logic.pdmi.ras.ru\/~yura\/en\/diplomen.pdf"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Lifshits, Y., Lohrey, M.: Querying and Embedding Compressed Texts (to appear, 2005)","DOI":"10.1007\/11821069_59"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1007\/978-3-540-27836-8_76","volume-title":"Automata, Languages and Programming","author":"M. Lohrey","year":"2004","unstructured":"Lohrey, M.: Word problems on compressed word. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 906\u2013918. Springer, Heidelberg (2004)"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/3-540-45465-9_6","volume-title":"Automata, Languages and Programming","author":"H. Mannila","year":"2002","unstructured":"Mannila, H.: Local and Global Methods in Data Mining: Basic Techniques and open Problems. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 57\u201368. Springer, Heidelberg (2002)"},{"issue":"1","key":"15_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.ipl.2004.01.002","volume":"90","author":"N. Markey","year":"2004","unstructured":"Markey, N., Schnoebelen, P.: A PTIME-complete matching problem for SLP-compressed words. Information Processing Letters\u00a090(1), 3\u20136 (2004)","journal-title":"Information Processing Letters"},{"key":"#cr-split#-15_CR13.1","unstructured":"Matiyasevich, Y.: Real-time recognition of the inclusion relation. Zapiski Nauchnykh Leningradskovo Otdeleniya Mat. Inst. Steklova Akad. Nauk SSSR??20, 104???114 (1971);"},{"key":"#cr-split#-15_CR13.2","unstructured":"Translated into English, Journal of Soviet Mathematics 1, 64???70 (1973), http:\/\/logic.pdmi.ras.ru\/~yumat\/Journal"},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/3-540-47849-3_3","volume-title":"SOFSEM\u201999: Theory and Practice of Informatics","author":"W. Rytter","year":"1999","unstructured":"Rytter, W.: Algorithms on compressed strings and arrays. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol.\u00a01725, pp. 48\u201365. Springer, Heidelberg (1999)"},{"issue":"299","key":"15_CR15","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1016\/S0304-3975(02)00590-X","volume":"1-3","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. TCS\u00a01-3(299), 763\u2013774 (2003)","journal-title":"TCS"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/3-540-08921-7_97","volume-title":"Mathematical Foundations of Computer Science 1978","author":"A. Slissenko","year":"1978","unstructured":"Slissenko, A.: String-matching in real time. In: Winkowski, J. (ed.) MFCS 1978. LNCS, vol.\u00a064, pp. 493\u2013496. Springer, Heidelberg (1978)"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Welch, T.: A technique for high performance data compresssion. Computer, 8\u201319 (June 1984)","DOI":"10.1109\/MC.1984.1659158"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11753728_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:03:29Z","timestamp":1619492609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11753728_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540341666","9783540341680"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11753728_15","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11753728","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}