{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T05:10:03Z","timestamp":1748581803097,"version":"3.41.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319236599"},{"type":"electronic","value":"9783319236605"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23660-5_2","type":"book-chapter","created":{"date-parts":[[2015,8,26]],"date-time":"2015-08-26T12:05:10Z","timestamp":1440590710000},"page":"14-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Equality Testing of Compressed Strings"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,27]]},"reference":[{"issue":"4","key":"2_CR1","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1145\/792538.792540","volume":"50","author":"M Agrawal","year":"2003","unstructured":"Agrawal, M., Biswas, S.: Primality and identity testing via chinese remaindering. J. Assoc. Comput. Mach. 50(4), 429\u2013443 (2003)","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR2","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Proceedings of SODA 2000, pp. 819\u2013828. ACM\/SIAM (2000)"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/3-540-60084-1_75","volume-title":"Automata, Languages and Programming","author":"JL Balc\u00e1zar","year":"1995","unstructured":"Balc\u00e1zar, J.L.: The complexity of searching succinctly represented graphs. In: F\u00fcl\u00f6p, Z. (ed.) ICALP 1995. LNCS, vol. 944, pp. 208\u2013219. Springer, Heidelberg (1995)"},{"issue":"2","key":"2_CR4","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. J. Comput. Syst. Sci. 65(2), 332\u2013350 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"2_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0020-0190(96)00096-8","volume":"59","author":"B Borchert","year":"1996","unstructured":"Borchert, B., Lozano, A.: Succinct circuit representations and leaf language classes are basically the same concept. Inf. Process. Lett. 59(4), 211\u2013215 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"7","key":"2_CR6","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., Lehman, A., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"2_CR7","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1137\/0218066","volume":"18","author":"W Eberly","year":"1989","unstructured":"Eberly, W.: Very fast parallel polynomial arithmetic. SIAM J. Comput. 18(5), 955\u2013976 (1989)","journal-title":"SIAM J. Comput."},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Fich, F.E., Tompa, M.: The parallel complexity of exponentiating polynomials over finite fields. In: Proceedings of STOC 1985, pp. 38\u201347. ACM (1985)","DOI":"10.1145\/22145.22150"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"NJ Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16, 109\u2013114 (1965)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"2_CR10","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H Galperin","year":"1983","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Control 56(3), 183\u2013198 (1983)","journal-title":"Inf. Control"},{"key":"2_CR11","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 \u201996","author":"L Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding (extended abstract). In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-61258-0_3","volume-title":"Combinatorial Pattern Matching","author":"L Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Randomized efficient algorithms for compressed strings: the finger-print approach (extended abstract). In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol. 1075, pp. 39\u201349. Springer, Heidelberg (1996)"},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-24583-1_27","volume-title":"String Processing and Information Retrieval","author":"K Goto","year":"2011","unstructured":"Goto, K., Bannai, H., Inenaga, S., Takeda, M.: Fast q-gram mining on SLP\u00a0compressed\u00a0strings. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol. 7024, pp. 278\u2013289. Springer, Heidelberg (2011)"},{"key":"2_CR14","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"R Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial-time algorithm for deciding equivalence of normed context-free processes. In: Proceedings of FOCS 1994, pp. 623\u2013631. IEEE Computer Society (1994)","DOI":"10.1109\/SFCS.1994.365729"},{"issue":"1&2","key":"2_CR16","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theor. Comput. Sci. 158(1&2), 143\u2013159 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR17","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. 7391, pp. 533\u2013544. Springer, Heidelberg (2012)"},{"key":"2_CR18","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. In: Proceedings of STACS 2013. LIPIcs, vol. 20, pp. 233\u2013244. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013)"},{"key":"2_CR19","unstructured":"Je\u017c, A., Lohrey, M.: Approximation of smallest linear tree grammars. Technical report, arXiv.org (2014). http:\/\/arxiv.org\/abs\/1309.4958"},{"issue":"1\u20132","key":"2_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13(1\u20132), 1\u201346 (2004)","journal-title":"Comput. Complex."},{"key":"2_CR21","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 Karpinski","year":"1995","unstructured":"Karpinski, M., Rytter, W.: Pattern-matching for strings with short descriptions. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol. 937, pp. 205\u2013214. Springer, Heidelberg (1995)"},{"key":"2_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-662-48054-0_37","volume-title":"Mathematical Foundations of Computer Science 2015","author":"D K\u00f6nig","year":"2015","unstructured":"K\u00f6nig, D., Lohrey, M.: Parallel identity testing for skew circuits with big powers and applications. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 445\u2013458. Springer, Heidelberg (2015)"},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-73437-6_24","volume-title":"Combinatorial Pattern Matching","author":"Y Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: a tractability border. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 228\u2013240. Springer, Heidelberg (2007)"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/11821069_59","volume-title":"Mathematical Foundations of Computer Science 2006","author":"Y Lifshits","year":"2006","unstructured":"Lifshits, Y., Lohrey, M.: Querying and embedding compressed texts. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 681\u2013692. Springer, Heidelberg (2006)"},{"issue":"2","key":"2_CR25","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptology 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptology"},{"key":"2_CR26","series-title":"SpringerBriefs in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The Compressed Word Problem for Groups","author":"M Lohrey","year":"2014","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer, Heidelberg (2014)"},{"key":"2_CR27","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality-tests in polylogarithmic time. In: Proceedings of SODA 1994, pp. 213\u2013222. ACM\/SIAM (1994)"},{"issue":"2","key":"2_CR28","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"},{"key":"2_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-63220-4_45","volume-title":"Combinatorial Pattern Matching","author":"M Miyazaki","year":"1997","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. In: Hein, J., Apostolico, A. (eds.) CPM 1997. LNCS, vol. 1264, pp. 1\u201311. Springer, Heidelberg (1997)"},{"issue":"3","key":"2_CR30","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"CH Papadimitriou","year":"1986","unstructured":"Papadimitriou, C.H., Yannakakis, M.: A note on succinct representations of graphs. Inform. Control 71(3), 181\u2013185 (1986)","journal-title":"Inform. Control"},{"key":"2_CR31","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. 855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"issue":"8\u20139","key":"2_CR32","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.ipl.2012.01.008","volume":"112","author":"M Schmidt-Schau\u00df","year":"2012","unstructured":"Schmidt-Schau\u00df, M., Schnitger, G.: Fast equality test for straight-line compressed strings. Inf. Process. Lett. 112(8\u20139), 341\u2013345 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"2_CR33","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2_CR34","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1006\/inco.1997.2696","volume":"142","author":"H Veith","year":"1998","unstructured":"Veith, H.: Succinct representation, leaf languages, and projection reductions. Inf. Comput. 142(2), 207\u2013236 (1998)","journal-title":"Inf. Comput."},{"key":"2_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Combinatorics on Words"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23660-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T04:48:12Z","timestamp":1748580492000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23660-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319236599","9783319236605"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23660-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"27 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}