{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:07Z","timestamp":1760202727747,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_25","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"331-345","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Compressed Indexing with Signature Grammars"],"prefix":"10.1007","author":[{"given":"Anders Roy","family":"Christiansen","sequence":"first","affiliation":[]},{"given":"Mikko Berggren","family":"Ettienne","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"25_CR1","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Proceedings of the 11th Annual Symposium on Discrete Algorithms. Citeseer (2000)"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-642-15775-2_37","volume-title":"Algorithms \u2013 ESA 2010","author":"D Belazzougui","year":"2010","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Fast prefix search in little space, with applications. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6346, pp. 427\u2013438. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15775-2_37"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Bille, P., Ettienne, M.B., G\u00f8rtz, I.L., Vildh\u00f8j, H.W.: Time-space trade-offs for Lempel-Ziv compressed indexing. In: 28th Annual Symposium on Combinatorial Pattern Matching. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2017)","DOI":"10.1016\/j.tcs.2017.12.021"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of the 27th SOCG, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"1","key":"25_CR5","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986)","journal-title":"Inf. Control"},{"issue":"4","key":"25_CR6","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/PL00009202","volume":"20","author":"M Farach","year":"1998","unstructured":"Farach, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. Algorithmica 20(4), 388\u2013404 (1998)","journal-title":"Algorithmica"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: Blasting through the information theoretic barrier with fusion trees. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 1\u20137. ACM, New York (1990)","DOI":"10.1145\/100216.100217"},{"key":"25_CR8","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). https:\/\/doi.org\/10.1007\/978-3-642-28332-1_21"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-642-54423-1_63","volume-title":"LATIN 2014: Theoretical Informatics","author":"T Gagie","year":"2014","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 731\u2013742. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54423-1_63"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Optimal-time text indexing in BWT-runs bounded space. arXiv preprint arXiv:1705.10382 (2017)","DOI":"10.1137\/1.9781611975031.96"},{"key":"25_CR11","unstructured":"Gawrychowski, P., Karczmarz, A., Kociumaka, T., \u0141\u0105cki, J., Sankowski, P.: Optimal dynamic strings. arXiv preprint arXiv:1511.02612 (2015)"},{"issue":"3","key":"25_CR12","first-page":"20","volume":"11","author":"A Je\u017c","year":"2015","unstructured":"Je\u017c, A.: Faster fully compressed pattern matching by recompression. ACM Trans. Algorithms (TALG) 11(3), 20 (2015)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"25_CR13","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proceedings of the 3rd South American Workshop on String Processing (WSP 1996), vol. 26, no. (Teollisuuskatu 23), pp. 141\u2013155 (1996)"},{"issue":"2","key":"25_CR14","doi-asserted-by":"publisher","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. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"issue":"2","key":"25_CR15","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 17(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"25_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv. (CSUR) 39(1), 2 (2007)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"25_CR17","unstructured":"Nishimoto, T., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Dynamic index, LZ factorization, and LCE queries in compressed space. arXiv preprint arXiv:1504.06954 (2015)"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: Proceedings of the 50th FOCS, pp. 315\u2013323 (2009)","DOI":"10.1109\/FOCS.2009.11"},{"key":"25_CR19","unstructured":"Sahinalp, S.C., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: Proceedings of 37th Conference on Foundations of Computer Science, October 1996"},{"key":"25_CR20","unstructured":"Tomohiro, I.: Longest common extension with recompression (2017)"},{"issue":"3","key":"25_CR21","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 Trans. Inf. Theory 23(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:02:35Z","timestamp":1709827355000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}