{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:45:44Z","timestamp":1725795944227},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319075655"},{"type":"electronic","value":"9783319075662"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07566-2_5","type":"book-chapter","created":{"date-parts":[[2014,6,12]],"date-time":"2014-06-12T03:50:31Z","timestamp":1402545031000},"page":"40-49","source":"Crossref","is-referenced-by-count":2,"title":["Compressed Subsequence Matching and Packed\u00a0Tree\u00a0Coloring"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick Hagge","family":"Cording","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"5_CR1","doi-asserted-by":"publisher","first-page":"1295","DOI":"10.1137\/S0097539703437211","volume":"35","author":"S. Abiteboul","year":"2006","unstructured":"Abiteboul, S., Alstrup, S., Kaplan, H., Milo, T., Rauhe, T.: Compact labeling scheme for ancestor queries. SIAM J. Comput.\u00a035(6), 1295\u20131309 (2006)","journal-title":"SIAM J. Comput."},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Automata, Languages and Programming","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 73\u201384. Springer, Heidelberg (2000)"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-63165-8_184","volume-title":"Automata, Languages and Programming","author":"S. Alstrup","year":"1997","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 270\u2013280. Springer, Heidelberg (1997)"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proc. 39th FOCS, pp. 534\u2013543 (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"issue":"4","key":"5_CR5","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0020-0190(97)00170-1","volume":"64","author":"S. Alstrup","year":"1997","unstructured":"Alstrup, S., Secher, J.P., Spork, M.: Optimal on-line decremental connectivity in trees. Inform. Process. Lett.\u00a064(4), 161\u2013164 (1997)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"5_CR6","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"R.A. Baeza-Yates","year":"1991","unstructured":"Baeza-Yates, R.A.: Searching subsequences. Theoret. Comput. Sci.\u00a078(2), 363\u2013376 (1991)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"5_CR7","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theoret. Comput. Sci.\u00a0321(1), 5\u201312 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"5_CR8","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. Comput. System Sci.\u00a048(2), 214\u2013230 (1994)","journal-title":"J. Comput. System Sci."},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings. In: Proc. 22nd SODA, pp. 373\u2013389 (2011)","DOI":"10.1137\/1.9781611973082.30"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Boasson, L., Cegielski, P., Guessarian, I., Matiyasevich, Y.: Window-accumulated subsequence matching problem is linear. In: Proc. 18th PODS, pp. 327\u2013336 (1999)","DOI":"10.1145\/303976.304008"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/11753728_15","volume-title":"Computer Science \u2013 Theory and Applications","author":"P. C\u00e9gielski","year":"2006","unstructured":"C\u00e9gielski, P., Guessarian, I., Lifshits, Y., Matiyasevich, Y.V.: Window subsequence problems for compressed texts. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol.\u00a03967, pp. 127\u2013136. Springer, Heidelberg (2006)"},{"issue":"6","key":"5_CR12","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.ipl.2006.02.008","volume":"98","author":"P. C\u00e9gielski","year":"2006","unstructured":"C\u00e9gielski, P., Guessarian, I., Matiyasevich, Y.: Multiple serial episodes matching. Inform. Process. Lett.\u00a098(6), 211\u2013218 (2006)","journal-title":"Inform. Process. Lett."},{"issue":"7","key":"5_CR13","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 Trans. Inf. Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"5_CR14","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S1570-8667(03)00029-7","volume":"1","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Melichar, B., Tron\u00ed\u010dek, Z.: Directed acyclic subsequence graph-overview. J. Discrete Algorithms\u00a01(3), 255\u2013280 (2003)","journal-title":"J. Discrete Algorithms"},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/3-540-63220-4_46","volume-title":"Combinatorial Pattern Matching","author":"G. Das","year":"1997","unstructured":"Das, G., Fleischer, R., Gasieniec, L., Gunopulos, D., K\u00e4rkk\u00e4inen, J.: Episode matching. In: Hein, J., Apostolico, A. (eds.) CPM 1997. LNCS, vol.\u00a01264, pp. 12\u201327. Springer, Heidelberg (1997)"},{"key":"5_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BFb0028247","volume-title":"Algorithms and Data Structures","author":"P.F. Dietz","year":"1991","unstructured":"Dietz, P.F.: Finding level-ancestors in dynamic trees. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1991. LNCS, vol.\u00a0519, pp. 32\u201340. Springer, Heidelberg (1991)"},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/3-540-61680-2_50","volume-title":"Algorithms - ESA \u201996","author":"P. Ferragina","year":"1996","unstructured":"Ferragina, P., Muthukrishnan, S.: Efficient dynamic method-lookup for object oriented languages. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol.\u00a01136, pp. 107\u2013120. Springer, Heidelberg (1996)"},{"issue":"3","key":"5_CR18","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. System Sci.\u00a047(3), 424\u2013436 (1993)","journal-title":"J. Comput. System Sci."},{"issue":"11","key":"5_CR19","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"N.J. Larsson","year":"2000","unstructured":"Larsson, N.J., Moffat, A.: Off-line dictionary-based compression. Proc. IEEE\u00a088(11), 1722\u20131732 (2000)","journal-title":"Proc. IEEE"},{"issue":"3","key":"5_CR20","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1023\/A:1009748302351","volume":"1","author":"H. Mannila","year":"1997","unstructured":"Mannila, H., Toivonen, H., Verkamo, A.I.: Discovery of frequent episodes in event sequences. Data Min. Knowl. Discov.\u00a01(3), 259\u2013289 (1997)","journal-title":"Data Min. Knowl. Discov."},{"key":"5_CR21","unstructured":"Muthukrishnan, S., M\u00fcller, M.: Time and space efficient method-lookup for object-oriented programs. In: Proc. 7th SODA, pp. 42\u201351 (1996)"},{"issue":"1","key":"5_CR22","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\u2013Ziv factorization to the approximation of grammar-based compression. Theoret. Comput. Sci.\u00a0302(1), 211\u2013222 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"5_CR23","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Endre Tarjan, R.: A data structure for dynamic trees. J. Comput. System Sci.\u00a026(3), 362\u2013391 (1983)","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"5_CR24","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jagm.2002.1211","volume":"42","author":"M. Thorup","year":"2002","unstructured":"Thorup, M.: Randomized sorting in O(nloglogn) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms\u00a042(2), 205\u2013230 (2002)","journal-title":"J. Algorithms"},{"issue":"5","key":"5_CR25","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/s10958-009-9396-0","volume":"158","author":"A. Tiskin","year":"2009","unstructured":"Tiskin, A.: Faster subsequence recognition in compressed strings. J. Math. Sci.\u00a0158(5), 759\u2013769 (2009)","journal-title":"J. Math. Sci."},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-642-20712-9_32","volume-title":"Computer Science \u2013 Theory and Applications","author":"A. Tiskin","year":"2011","unstructured":"Tiskin, A.: Towards approximate matching in compressed strings: Local subsequence recognition. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 401\u2013414. Springer, Heidelberg (2011)"},{"key":"5_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-48194-X_12","volume-title":"Combinatorial Pattern Matching","author":"Z. Tron\u00ed\u010dek","year":"2001","unstructured":"Tron\u00ed\u010dek, Z.: Episode matching. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 143\u2013146. Springer, Heidelberg (2001)"},{"key":"5_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-21458-5_27","volume-title":"Combinatorial Pattern Matching","author":"T. Yamamoto","year":"2011","unstructured":"Yamamoto, T., Bannai, H., Inenaga, S., Takeda, M.: Faster subsequence and don\u2019t-care pattern matching on compressed texts. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 309\u2013322. Springer, Heidelberg (2011)"},{"issue":"3","key":"5_CR29","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\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"5_CR30","doi-asserted-by":"publisher","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. Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07566-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,20]],"date-time":"2019-01-20T22:56:25Z","timestamp":1548024985000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07566-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075655","9783319075662"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07566-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}