{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T23:59:56Z","timestamp":1740095996233,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642389047"},{"type":"electronic","value":"9783642389054"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_17","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T23:28:54Z","timestamp":1368660534000},"page":"165-176","source":"Crossref","is-referenced-by-count":13,"title":["Approximation of Grammar-Based Compression via Recompression"],"prefix":"10.1007","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"7","key":"17_CR1","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Transactions on Information Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"17_CR2","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M. Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM\u00a047(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-642-23719-5_36","volume-title":"Algorithms \u2013 ESA 2011","author":"P. Gawrychowski","year":"2011","unstructured":"Gawrychowski, P.: Pattern matching in Lempel-Ziv compressed strings: Fast, simple, and deterministic. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 421\u2013432. Springer, Heidelberg (2011)"},{"key":"17_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 1996","author":"L. G\u0105sieniec","year":"1996","unstructured":"G\u0105sieniec, L., Karpi\u0144ski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-642-31594-7_45","volume-title":"Automata, Languages, and Programming","author":"A. Je\u017c","year":"2012","unstructured":"Je\u017c, A.: Faster fully compressed pattern matching by recompression. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 533\u2013544. Springer, Heidelberg (2012)"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: The complexity of compressed membership problems for finite automata. Theory of Computing Systems, 1\u201334 (2013), \n                  \n                    http:\/\/dx.doi.org\/10.1007\/s00224-013-9443-6","DOI":"10.1007\/s00224-013-9443-6"},{"key":"17_CR7","first-page":"233","volume-title":"30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics (LIPIcs)","author":"A. Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. In: Portier, N., Wilke, T. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a020, pp. 233\u2013244. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2013), \n                  \n                    http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2013\/3937"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/978-3-642-34109-0_34","volume-title":"String Processing and Information Retrieval","author":"J. K\u00e4rkk\u00e4inen","year":"2012","unstructured":"K\u00e4rkk\u00e4inen, J., Mikkola, P., Kempa, D.: Grammar precompression speeds up Burrows\u2013Wheeler compression. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol.\u00a07608, pp. 330\u2013335. Springer, Heidelberg (2012)"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-60044-2_44","volume-title":"Combinatorial Pattern Matching","author":"M. Karpi\u0144ski","year":"1995","unstructured":"Karpi\u0144ski, M., Rytter, W., Shinohara, A.: Pattern-matching for strings with short descriptions. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol.\u00a0937, pp. 205\u2013214. Springer, Heidelberg (1995)"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference, pp. 296\u2013305. IEEE Computer Society (1999)","DOI":"10.1109\/DCC.1999.755679"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-20712-9_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M., Mathissen, C.: Compressed membership in automata with compressed labels. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 275\u2013288. Springer, Heidelberg (2011)"},{"issue":"2","key":"17_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02522825","volume":"17","author":"K. Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica\u00a017(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"key":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA 1994","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":"1-3","key":"17_CR14","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-3), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"2-4","key":"17_CR15","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","volume":"3","author":"H. Sakamoto","year":"2005","unstructured":"Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based compression. J. Discrete Algorithms\u00a03(2-4), 416\u2013430 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Storer, J.A., Szymanski, T.G.: The macro model for data compression. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) STOC, pp. 30\u201339. ACM (1978)","DOI":"10.1145\/800133.804329"}],"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-38905-4_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T21:59:39Z","timestamp":1557698379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}