{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:16Z","timestamp":1775281216786,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540734369","type":"print"},{"value":"9783540734376","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73437-6_24","type":"book-chapter","created":{"date-parts":[[2007,8,13]],"date-time":"2007-08-13T17:36:44Z","timestamp":1187026604000},"page":"228-240","source":"Crossref","is-referenced-by-count":44,"title":["Processing Compressed Texts: A Tractability Border"],"prefix":"10.1007","author":[{"given":"Yury","family":"Lifshits","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: Pattern matching in Z-compressed files. In: SODA 1994 (1994)"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/978-3-540-45078-8_30","volume-title":"Algorithms and Data Structures","author":"A. Amir","year":"2003","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 340\u2013352. Springer, Heidelberg (2003)"},{"issue":"1","key":"24_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(91)90056-N","volume":"39","author":"A. Apostolico","year":"1991","unstructured":"Apostolico, A., Farach, M., Iliopoulos, C.S.: Optimal superprimitivity testing for strings. Inf. Process. Lett.\u00a039(1), 17\u201320 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"24_CR4","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.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":"24_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"Computer Science \u2013 Theory and Applications","author":"P. Cegielski","year":"2006","unstructured":"Cegielski, P., Guessarian, I., Lifshits, Y., Matiyasevich, Y.: Window subsequence problems for compressed texts. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol.\u00a03967, Springer, Heidelberg (2006)"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1145\/225058.225288","volume-title":"STOC 1995","author":"M. Farach","year":"1995","unstructured":"Farach, M., Thorup, M.: String matching in lempel-ziv compressed strings. In: STOC 1995, pp. 703\u2013712. ACM Press, New York (1995)"},{"key":"24_CR7","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman (1979)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/3-540-61422-2_148","volume-title":"Algorithm Theory - SWAT \u201996","author":"L. Ga\u0327sieniec","year":"1996","unstructured":"Ga\u0327sieniec, 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":"24_CR9","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)"},{"key":"24_CR10","first-page":"132","volume-title":"SPIRE 2000","author":"M. Hirao","year":"2000","unstructured":"Hirao, M., Shinohara, A., Takeda, M., Arikawa, S.: Fully compressed pattern matching algorithm for balanced straight-line programs. In: SPIRE 2000, pp. 132\u2013138. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-45123-4_18","volume-title":"Combinatorial Pattern Matching","author":"J. K\u00e4rkk\u00e4inen","year":"2000","unstructured":"K\u00e4rkk\u00e4inen, J., Navarro, G., Ukkonen, E.: Approximate string matching over Ziv-Lempel compressed text. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 195\u2013209. Springer, Heidelberg (2000)"},{"key":"24_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/3-540-60044-2_44","volume-title":"Combinatorial Pattern Matching","author":"M. Karpinski","year":"1995","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: Pattern-matching for strings with short descriptions. In: Galil, Z., Ukkonen, E. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a0937, pp. 205\u2013214. Springer, Heidelberg (1995)"},{"issue":"1","key":"24_CR13","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0304-3975(02)00426-7","volume":"298","author":"T. Kida","year":"2003","unstructured":"Kida, T., Matsumoto, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Collage system: a unifying framework for compressed pattern matching. Theor. Comput. Sci.\u00a0298(1), 253\u2013272 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/11821069_56","volume-title":"Mathematical Foundations of Computer Science 2006","author":"S. Lasota","year":"2006","unstructured":"Lasota, S., Rytter, W.: Faster algorithm for bisimulation equivalence of normed context-free processes. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 646\u2013657. Springer, Heidelberg (2006)"},{"key":"24_CR15","unstructured":"Lifshits, Y.: Algorithmic properties of compressed texts. Technical Report PDMI, 23\/2006 (2006)"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/11821069_59","volume-title":"Mathematical Foundations of Computer Science 2006","author":"Y. Lifshits","year":"2006","unstructured":"Lifshits, Y., Lohrey, M.: Quering and embedding compressed texts. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 681\u2013692. Springer, Heidelberg (2006)"},{"key":"24_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"24_CR18","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Combinatorial Pattern Matching","author":"M. Miyazaki","year":"1997","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight line programs. In: Hein, J., Apostolico, A. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a01264, pp. 1\u201311. Springer, Heidelberg (1997)"},{"issue":"5-6","key":"24_CR19","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/S1570-8667(03)00036-4","volume":"1","author":"G. Navarro","year":"2003","unstructured":"Navarro, G.: Regular expression searching on compressed text. J. of Discrete Algorithms\u00a01(5-6), 423\u2013443 (2003)","journal-title":"J. of Discrete Algorithms"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/3-540-48452-3_2","volume-title":"Combinatorial Pattern Matching","author":"G. Navarro","year":"1999","unstructured":"Navarro, G., Raffinot, M.: A general practical approach to pattern matching over Ziv-Lempel compressed text. In: Crochemore, M., Paterson, M.S. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a01645, pp. 14\u201336. Springer, Heidelberg (1999)"},{"key":"24_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1007\/11821069_64","volume-title":"Mathematical Foundations of Computer Science 2006","author":"A. Pagourtzis","year":"2006","unstructured":"Pagourtzis, A., Zachos, S.: The complexity of counting functions with easy decision version. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 741\u2013752. Springer, Heidelberg (2006)"},{"key":"24_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"issue":"3","key":"24_CR23","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/990308.990312","volume":"51","author":"W. Plandowski","year":"2004","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J. ACM\u00a051(3), 483\u2013496 (2004)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"24_CR24","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci.\u00a0302(1\u20133), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-540-27836-8_5","volume-title":"Automata, Languages and Programming","author":"W. Rytter","year":"2004","unstructured":"Rytter, W.: Grammar compression, LZ-encodings, and string algorithms with implicit input. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 15\u201327. Springer, Heidelberg (2004)"},{"issue":"3","key":"24_CR26","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73437-6_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:12:08Z","timestamp":1619518328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73437-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734369","9783540734376"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73437-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}