{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:42:51Z","timestamp":1787506971732,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_5","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"15-27","source":"Crossref","is-referenced-by-count":30,"title":["Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input"],"prefix":"10.1007","author":[{"given":"Wojciech","family":"Rytter","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"5_CR1","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern-matching in Zcompressed files. In: SODA (1994)"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient two dimensional compressed matching. In: Proc. of the 2nd IEEE Data Compression Conference, pp. 279\u2013288 (1992)","DOI":"10.1109\/DCC.1992.227453"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/3-540-58201-0_70","volume-title":"Automata, Languages, and Programming","author":"A. Amir","year":"1994","unstructured":"Amir, A., Benson, G., Farach, M.: Optimal two-dimensional compressed matching. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 215\u2013225. Springer, Heidelberg (1994)"},{"issue":"1","key":"5_CR4","first-page":"46","volume":"21","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J.C.S.S.\u00a021(1), 46\u201362 (1980)","journal-title":"J.C.S.S."},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Leonardi, S.: Some theory and practice of greedy off-line textual substitution. In: DCC 1998, pp. 119\u2013128 (1998)","DOI":"10.1109\/DCC.1998.672138"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A., Shelat, A.: Approximating The Smallest Grammar: Kolmogorov Complexity in Natural Models. In: STOC 2002 (2002)","DOI":"10.1145\/509907.510021"},{"key":"5_CR7","volume-title":"Handbook of Formal Languages","author":"C. Choffrut","year":"1997","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Combinatorics of words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Springer, Heidelberg (1997)"},{"key":"5_CR8","volume-title":"Jewels of stringology - Text algorithms","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Rytter, W.: Jewels of stringology - Text algorithms. World Scientific, Singapore (2003)"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","volume-title":"Mathematical Foundations of Computer Science 1994","author":"S. Eyono Obono","year":"1994","unstructured":"Eyono Obono, S., Goralcik, P., Maksimenko, M.: Efficient solving of the word equations in one variable. In: Privara, I., Ru\u017ei\u010dka, P., Rovan, B. (eds.) MFCS 1994. LNCS, vol.\u00a0841, Springer, Heidelberg (1994)"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Farah, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. In: STOC 1995, pp. 703\u2013712 (1995)","DOI":"10.1145\/225058.225288"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: FOCS 1997 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"key":"5_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"5_CR13","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., Karpi\u0144ski, M., Plandowski, W., Rytter, W.: Efficient algorithms for compressed strings. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/3-540-61258-0_3","volume-title":"Combinatorial Pattern Matching","author":"L. Ga\u0327sieniec","year":"1996","unstructured":"Ga\u0327sieniec, L., Karpi\u0144ski, M., Plandowski, W., Rytter, W.: Randomized Efficient Algorithms for Compressed Strings: the finger-print approach. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 39\u201349. Springer, Heidelberg (1996)"},{"key":"5_CR15","volume-title":"Data Compression Conference","author":"L. Gasieniec","year":"1999","unstructured":"Gasieniec, L., Rytter, W.: Almost optimal fully compressed LZW-matching. In: Data Compression Conference, IEEE Computer Society, Los Alamitos (1999)"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Gasieniec, L., Gibbons, A., Rytter, W.: The parallel complexity of pattern-searching in highly compressed texts. In: MFCS (1999)","DOI":"10.1007\/3-540-48340-3_5"},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1109\/SPIRE.2000.878188","volume-title":"Proc. of 7th International Symposium on String Processing and Information Retrieval (SPIRE 2000)","author":"M. Hirao","year":"2000","unstructured":"Hirao, M., Shinohara, A., Takeda, M., Arikawa, S.: Faster fully compressed pattern matching algorithm for balanced straight-line programs. In: Proc. of 7th International Symposium on String Processing and Information Retrieval (SPIRE 2000), September 2000, pp. 132\u2013138. IEEE Computer Society, Los Alamitos (2000)"},{"key":"5_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/3-540-63165-8_168","volume-title":"Automata, Languages and Programming","author":"J. Karhum\u00e4ki","year":"1997","unstructured":"Karhum\u00e4ki, J., Mignosi, F., Plandowski, W.: The expressibility of languages and relations by word equations. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 98\u2013109. Springer, Heidelberg (1997)"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"J. Karkkainen","year":"2003","unstructured":"Karkkainen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, Springer, Heidelberg (2003)"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: Pattern-matching for strings with short description. In: Combinatorial Pattern Matching (1995)","DOI":"10.1007\/3-540-60044-2_44"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Kida, T., Shibara, Y., Takeda, M., Shinohara, A., Arikawa, S.: A unifying framework for compressed pattern matching. In: SPIRE 1999 (1999)","DOI":"10.1109\/SPIRE.1999.796582"},{"key":"5_CR22","volume-title":"The Art of Computing","author":"D. Knuth","year":"1981","unstructured":"Knuth, D.: The Art of Computing, 2nd edn. Addison-Wesley, Reading (1981)","edition":"2"},{"issue":"4","key":"5_CR23","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1145\/234533.234543","volume":"43","author":"A. Koscielski","year":"1996","unstructured":"Koscielski, A., Pacholski, L.: Complexity of Makanin\u2019s algorithm, J. ACM\u00a043(4), 670\u2013684 (1996)","journal-title":"ACM"},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"J. Kieffer","year":"2000","unstructured":"Kieffer, J., Yang, E.: Grammar-based codes: a new class of universal lossless source codes. IEEE Trans. on Inf. Theory\u00a046, 737\u2013754 (2000)","journal-title":"IEEE Trans. on Inf. Theory"},{"key":"5_CR25","unstructured":"Lanctot, J.K.: Ming Li, En-hui Yang, Estimating DNA Sequence Entropy. In: SODA 2000 (2000)"},{"key":"5_CR26","unstructured":"Lehman, E., Shelat, A.: Approximation algorithms for grammar-based compression. In: SODA 2002 (2002)"},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"J. Lempel","year":"1976","unstructured":"Lempel, J.: Ziv, On the complexity of finite sequences. IEEE Trans. on Inf. Theory\u00a022, 75\u201381 (1976)","journal-title":"IEEE Trans. on Inf. Theory"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Lohrey, M.: Word problems on compressed words ICALP 2004 (2004)","DOI":"10.1007\/978-3-540-27836-8_76"},{"issue":"145","key":"5_CR29","first-page":"147","volume":"103","author":"G.S. Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Mat. Sb.\u00a0103(145), 147\u2013233 (1977)","journal-title":"Mat. Sb."},{"issue":"2","key":"5_CR30","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/248625.248639","volume":"15","author":"U. Manber","year":"1997","unstructured":"Manber, U.: A text compression scheme that allows fast searching directly in the compressed file. ACM Transactions on Information Systems\u00a015(2), 124\u2013136 (1997)","journal-title":"ACM Transactions on Information Systems"},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Markey, N., Schnoebelen, P.: A P-Time complete matching problem for SLPcompressed words. In: IPL 2004 (2004)","DOI":"10.1016\/j.ipl.2004.01.002"},{"key":"5_CR32","first-page":"187","volume":"1","author":"M. Miyazaki","year":"2000","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern-matching algorithm for strings in terms of straight-line programs. Journal of Discrete Algorithms\u00a01, 187\u2013204 (2000)","journal-title":"Journal of Discrete Algorithms"},{"key":"5_CR33","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in P-Space. JACM (2004)","DOI":"10.1145\/990308.990312"},{"key":"5_CR34","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)"},{"key":"5_CR35","volume-title":"Jewels forever","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of compressed recognition of formal languages. In: Karhumaki, J. (ed.) Jewels forever, Springer, Heidelberg (1999)"},{"key":"5_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/BFb0055097","volume-title":"Automata, Languages and Programming","author":"W. Plandowski","year":"1998","unstructured":"Plandowski, W., Rytter, W.: Applying Lempel-Ziv encodings to the solution of word equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, p. 731. Springer, Heidelberg (1998)"},{"issue":"299","key":"5_CR37","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); Preliminary version in Combinatorial Pattern Matching (June 2002)","journal-title":"TCS"},{"issue":"11","key":"5_CR38","doi-asserted-by":"publisher","first-page":"1769","DOI":"10.1109\/5.892712","volume":"88","author":"W. Rytter","year":"2000","unstructured":"Rytter, W.: Compressed and fully compressed pattern-matching in one and twodimensions. Proceedings of IEEE\u00a088(11), 1769\u20131778 (2000)","journal-title":"Proceedings of IEEE"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:23:58Z","timestamp":1605741838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}