{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T12:25:42Z","timestamp":1765974342625,"version":"3.37.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319674278"},{"type":"electronic","value":"9783319674285"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-67428-5_5","type":"book-chapter","created":{"date-parts":[[2017,9,5]],"date-time":"2017-09-05T01:22:24Z","timestamp":1504574544000},"page":"51-67","source":"Crossref","is-referenced-by-count":5,"title":["On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation"],"prefix":"10.1007","author":[{"given":"Golnaz","family":"Badkobeh","sequence":"first","affiliation":[]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[]},{"given":"Dmitry","family":"Kosolobov","sequence":"additional","affiliation":[]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,6]]},"reference":[{"key":"5_CR1","unstructured":"Supplementary materials for the present paper: C++ code for described experiments. https:\/\/bitbucket.org\/dkosolobov\/lzd-lzmw"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-16321-0_15","volume-title":"String Processing and Information Retrieval","author":"D Belazzougui","year":"2010","unstructured":"Belazzougui, D., Boldi, P., Vigna, S.: Dynamic Z-Fast tries. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 159\u2013172. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-16321-0_15"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-662-48350-3_13","volume-title":"Algorithms \u2013 ESA 2015","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Cording, P.H., Puglisi, S.J., Tabei, Y.: Access, rank, and select in grammar-compressed strings. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 142\u2013154. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48350-3_13"},{"issue":"3","key":"5_CR4","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"5_CR5","doi-asserted-by":"crossref","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 Trans. Inf. Theor. 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"3","key":"5_CR6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.3233\/FI-2011-565","volume":"111","author":"F Claude","year":"2011","unstructured":"Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fundamenta Informaticae 111(3), 313\u2013337 (2011)","journal-title":"Fundamenta Informaticae"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-28332-1_21","volume-title":"Language and Automata Theory and Applications","author":"T Gagie","year":"2012","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 240\u2013251. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-28332-1_21"},{"key":"5_CR8","doi-asserted-by":"publisher","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: LZD Factorization: simple and practical online grammar compression with variable-to-fixed encoding. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 219\u2013230. Springer, Cham (2015). doi: 10.1007\/978-3-319-19929-0_19","DOI":"10.1007\/978-3-319-19929-0_19"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-319-46049-9_4","volume-title":"String Processing and Information Retrieval","author":"D Hucke","year":"2016","unstructured":"Hucke, D., Lohrey, M., Reh, C.P.: The smallest grammar problem revisited. In: Inenaga, S., Sadakane, K., Sakai, T. (eds.) SPIRE 2016. LNCS, vol. 9954, pp. 35\u201349. Springer, Cham (2016). doi: 10.1007\/978-3-319-46049-9_4"},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"I, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Efficient Lyndon factorization of grammar compressed text. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 153\u2013164. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38905-4_16","DOI":"10.1007\/978-3-642-38905-4_16"},{"issue":"2","key":"5_CR11","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Devel. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Devel."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Kempa, D., Kosolobov, D.: LZ-End parsing in compressed space. In: Proceedings of Data Compression Conference (DCC), pp. 350\u2013359. IEEE (2017)","DOI":"10.1109\/DCC.2017.73"},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theoret. Comput. Sci. 483, 115\u2013133 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Miller, V.S., Wegman, M.N.: Variations on a theme by Ziv and Lempel. In: Apostolico, A., Galil, Z. (eds.) Proceedings of NATO Advanced Research Workshop on Combinatorial Algorithms on Words, NATO ASI, vol. 12, pp. 131\u2013140. Springer, Heidelberg (1985)","DOI":"10.1007\/978-3-642-82456-2_9"},{"issue":"1\u20133","key":"5_CR15","doi-asserted-by":"crossref","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. Theoret. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Tanaka, T., I, T., Inenaga, S., Bannai, H., Takeda, M.: Computing convolution on grammar-compressed text. In: Proceedings of Data Compression Conference (DCC), pp. 451\u2013460. IEEE (2013)","DOI":"10.1109\/DCC.2013.53"},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/3-540-55719-9_86","volume-title":"Automata, Languages and Programming","author":"J Westbrook","year":"1992","unstructured":"Westbrook, J.: Fast incremental planarity testing. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 342\u2013353. Springer, Heidelberg (1992). doi: 10.1007\/3-540-55719-9_86"},{"issue":"5","key":"5_CR18","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor. 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"3","key":"5_CR19","doi-asserted-by":"crossref","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 Trans. Inf. Theor. 23(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theor."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67428-5_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,17]],"date-time":"2020-10-17T03:02:27Z","timestamp":1602903747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67428-5_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319674278","9783319674285"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67428-5_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}