{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:19:55Z","timestamp":1743056395612,"version":"3.40.3"},"publisher-location":"Cham","reference-count":80,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030406073"},{"type":"electronic","value":"9783030406080"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[[2020]]},"DOI":"10.1007\/978-3-030-40608-0_4","type":"book-chapter","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:07:34Z","timestamp":1582589254000},"page":"44-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Recompression: Technique for Word Equations and Compressed Data"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4321-3105","authenticated-orcid":false,"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,25]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Shmoys, D.B. (ed.) SODA, pp. 819\u2013828. ACM\/SIAM (2000). https:\/\/doi.org\/10.1145\/338219.338645, http:\/\/dl.acm.org\/citation.cfm?id=338219.338645","DOI":"10.1145\/338219.338645"},{"issue":"4\u20135","key":"4_CR2","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.is.2008.01.004","volume":"33","author":"G Busatto","year":"2008","unstructured":"Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML document trees. Inf. Syst. 33(4\u20135), 456\u2013474 (2008)","journal-title":"Inf. Syst."},{"issue":"4","key":"4_CR3","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1002\/malq.19880340410","volume":"34","author":"JR B\u00fcchi","year":"1988","unstructured":"B\u00fcchi, J.R., Senger, S.: Definability in the existential theory of concatenation and undecidable extensions of this theory. Math. Log. Q. 34(4), 337\u2013342 (1988). https:\/\/doi.org\/10.1002\/malq.19880340410","journal-title":"Math. Log. Q."},{"key":"4_CR4","doi-asserted-by":"publisher","unstructured":"Charatonik, W., Pacholski, L.: Word equations with two variables. In: IWWERT, pp. 43\u201356 (1991). https:\/\/doi.org\/10.1007\/3-540-56730-5_30","DOI":"10.1007\/3-540-56730-5_30"},{"issue":"7","key":"4_CR5","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005). https:\/\/doi.org\/10.1109\/TIT.2005.850116","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"4_CR6","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1142\/S0218196716500363","volume":"26","author":"L Ciobanu","year":"2016","unstructured":"Ciobanu, L., Diekert, V., Elder, M.: Solution sets for equations over free groups are EDT0L languages. IJAC 26(5), 843\u2013886 (2016). https:\/\/doi.org\/10.1142\/S0218196716500363","journal-title":"IJAC"},{"issue":"4","key":"4_CR7","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1006\/jsco.1997.0185","volume":"25","author":"H Comon","year":"1998","unstructured":"Comon, H.: Completion of rewrite systems with membership constraints. Part I: deduction rules. J. Symb. Comput. 25(4), 397\u2013419 (1998). https:\/\/doi.org\/10.1006\/jsco.1997.0185","journal-title":"J. Symb. Comput."},{"issue":"4","key":"4_CR8","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jsco.1997.0186","volume":"25","author":"H Comon","year":"1998","unstructured":"Comon, H.: Completion of rewrite systems with membership constraints. Part II: constraint solving. J. Symb. Comput. 25(4), 421\u2013453 (1998). https:\/\/doi.org\/10.1006\/jsco.1997.0186","journal-title":"J. Symb. Comput."},{"key":"4_CR9","doi-asserted-by":"publisher","unstructured":"Creus, C., Gasc\u00f3n, A., Godoy, G.: One-context unification with STG-compressed terms is in NP. In: Tiwari, A. (ed.) 23rd International Conference on Rewriting Techniques and Applications (RTA 2012). LIPIcs, vol. 15, pp. 149\u2013164. Schloss Dagstuhl \u2013 Leibniz Zentrum fuer Informatik, Dagstuhl, Germany (2012). https:\/\/doi.org\/10.4230\/LIPIcs.RTA.2012.149, http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2012\/3490","DOI":"10.4230\/LIPIcs.RTA.2012.149"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-540-27836-8_36","volume-title":"Automata, Languages and Programming","author":"R Da\u0327browski","year":"2004","unstructured":"Da\u0327browski, R., Plandowski, W.: Solving two-variable word equations. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 408\u2013419. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27836-8_36"},{"issue":"4","key":"4_CR11","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s00453-009-9375-3","volume":"60","author":"R Da\u0327browski","year":"2011","unstructured":"Da\u0327browski, R., Plandowski, W.: On word equations in one variable. Algorithmica 60(4), 819\u2013828 (2011). https:\/\/doi.org\/10.1007\/s00453-009-9375-3","journal-title":"Algorithmica"},{"key":"4_CR12","doi-asserted-by":"publisher","unstructured":"Diekert, V., Elder, M.: Solutions of twisted word equations, EDT0L languages, and context-free groups. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) ICALP. LIPIcs, vol. 80, pp. 96:1\u201396:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.96","DOI":"10.4230\/LIPIcs.ICALP.2017.96"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Diekert, V., Guti\u00e9rrez, C., Hagenah, C.: The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inf. Comput. 202(2), 105\u2013140 (2005). http:\/\/dx.doi.org\/10.1016\/j.ic.2005.04.002","DOI":"10.1016\/j.ic.2005.04.002"},{"key":"4_CR14","doi-asserted-by":"publisher","unstructured":"Diekert, V., Je\u017c, A., Plandowski, W.: Finding all solutions of equations in free groups and monoids with involution. Inf. Comput. 251, 263\u2013286 (2016). https:\/\/doi.org\/10.1016\/j.ic.2016.09.009","DOI":"10.1016\/j.ic.2016.09.009"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"1047","DOI":"10.1142\/S0218196706003372","volume":"16","author":"V Diekert","year":"2006","unstructured":"Diekert, V., Muscholl, A.: Solvability of equations in free partially commutative groups is decidable. Int. J. Algebr. Comput. 16, 1047\u20131070 (2006). https:\/\/doi.org\/10.1142\/S0218196706003372. Conference version in Proceedings of ICALP 2001, pp. 543-554, LNCS 2076","journal-title":"Int. J. Algebr. Comput."},{"issue":"1","key":"4_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0304-3975(06)80003-4","volume":"87","author":"WM Farmer","year":"1991","unstructured":"Farmer, W.M.: Simple second-order languages for which unification is undecidable. Theor. Comput. Sci. 87(1), 25\u201341 (1991). https:\/\/doi.org\/10.1016\/S0304-3975(06)80003-4","journal-title":"Theor. Comput. Sci."},{"key":"4_CR17","doi-asserted-by":"publisher","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M.: Context matching for compressed terms. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24\u201327 June 2008, Pittsburgh, PA, USA, pp. 93\u2013102. IEEE Computer Society (2008). https:\/\/doi.org\/10.1109\/LICS.2008.17","DOI":"10.1109\/LICS.2008.17"},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/1970398.1970402","volume":"12","author":"A Gasc\u00f3n","year":"2011","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M.: Unification and matching on compressed terms. ACM Trans. Comput. Log. 12(4), 26 (2011). https:\/\/doi.org\/10.1145\/1970398.1970402","journal-title":"ACM Trans. Comput. Log."},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.jsc.2008.10.005","volume":"45","author":"A Gasc\u00f3n","year":"2010","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M., Tiwari, A.: Context unification with one context variable. J. Symb. Comput. 45(2), 173\u2013193 (2010). https:\/\/doi.org\/10.1016\/j.jsc.2008.10.005","journal-title":"J. Symb. Comput."},{"key":"4_CR20","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Karpi\u0144ski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: SWAT, pp. 392\u2013403 (1996). https:\/\/doi.org\/10.1007\/3-540-61422-2_148","DOI":"10.1007\/3-540-61422-2_148"},{"key":"4_CR21","doi-asserted-by":"publisher","unstructured":"Gasieniec, L., Karpi\u0144ski, M., Plandowski, W., Rytter, W.: Randomized efficient algorithms for compressed strings: the finger-print approach. In: CPM, pp. 39\u201349 (1996). https:\/\/doi.org\/10.1007\/3-540-61258-0_3","DOI":"10.1007\/3-540-61258-0_3"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Gasieniec, L., Rytter, W.: Almost optimal fully LZW-compressed pattern matching. In: DCC, pp. 316\u2013325. IEEE Computer Society (1999)","DOI":"10.1109\/DCC.1999.755681"},{"key":"4_CR23","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. 6942, pp. 421\u2013432. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23719-5_36"},{"key":"4_CR24","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P.: Tying up the loose ends in fully LZW-compressed pattern matching. In: D\u00fcrr, C., Wilke, T. (eds.) STACS. LIPIcs, vol. 14, pp. 624\u2013635. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2012). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.624","DOI":"10.4230\/LIPIcs.STACS.2012.624"},{"issue":"3","key":"4_CR25","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/2483699.2483705","volume":"9","author":"P Gawrychowski","year":"2013","unstructured":"Gawrychowski, P.: Optimal pattern matching in LZW compressed strings. ACM Trans. Algorithms 9(3), 25 (2013). https:\/\/doi.org\/10.1145\/2483699.2483705","journal-title":"ACM Trans. Algorithms"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(81)90040-2","volume":"13","author":"WD Goldfarb","year":"1981","unstructured":"Goldfarb, W.D.: The undecidability of the second-order unification problem. Theor. Comput. Sci. 13, 225\u2013230 (1981). https:\/\/doi.org\/10.1016\/0304-3975(81)90040-2","journal-title":"Theor. Comput. Sci."},{"key":"4_CR27","doi-asserted-by":"publisher","unstructured":"Guti\u00e9rrez, C.: Satisfiability of word equations with constants is in exponential space. In: FOCS, pp. 112\u2013119 (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743434","DOI":"10.1109\/SFCS.1998.743434"},{"issue":"6","key":"4_CR28","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1051\/ita:2000126","volume":"34","author":"L Ilie","year":"2000","unstructured":"Ilie, L., Plandowski, W.: Two-variable word equations. ITA 34(6), 467\u2013501 (2000). https:\/\/doi.org\/10.1051\/ita:2000126","journal-title":"ITA"},{"issue":"1","key":"4_CR29","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/78935.78938","volume":"37","author":"J Jaffar","year":"1990","unstructured":"Jaffar, J.: Minimal and complete word unification. J. ACM 37(1), 47\u201385 (1990)","journal-title":"J. ACM"},{"key":"4_CR30","doi-asserted-by":"publisher","unstructured":"Je\u017c, A.: The complexity of compressed membership problems for finite automata. Theory Comput. Syst. 55, 685\u2013718 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9443-6","DOI":"10.1007\/s00224-013-9443-6"},{"key":"4_CR31","doi-asserted-by":"publisher","unstructured":"Je\u017c, A.: Context unification is in PSPACE. In: Koutsoupias, E., Esparza, J., Fraigniaud, P. (eds.) ICALP. LNCS, vol. 8573, pp. 244\u2013255. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_21, full version at http:\/\/arxiv.org\/abs\/1310.4367","DOI":"10.1007\/978-3-662-43951-7_21"},{"key":"4_CR32","doi-asserted-by":"publisher","unstructured":"Je\u017c, A.: Approximation of grammar-based compression via recompression. Theor. Comput. Sci. 592, 115\u2013134 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.05.027","DOI":"10.1016\/j.tcs.2015.05.027"},{"issue":"3","key":"4_CR33","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/2631920","volume":"11","author":"A Je\u017c","year":"2015","unstructured":"Je\u017c, A.: Faster fully compressed pattern matching by recompression. ACM Trans. Algorithms 11(3), 20:1\u201320:43 (2015). https:\/\/doi.org\/10.1145\/2631920","journal-title":"ACM Trans. Algorithms"},{"key":"4_CR34","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.tcs.2015.12.032","volume":"616","author":"A Je\u017c","year":"2016","unstructured":"Je\u017c, A.: A really simple approximation of smallest grammar. Theor. Comput. Sci. 616, 141\u2013150 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.12.032","journal-title":"Theor. Comput. Sci."},{"key":"4_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-014-9931-3","volume":"74","author":"A Je\u017c","year":"2016","unstructured":"Je\u017c, A.: One-variable word equations in linear time. Algorithmica 74, 1\u201348 (2016). https:\/\/doi.org\/10.1007\/s00453-014-9931-3","journal-title":"Algorithmica"},{"issue":"1","key":"4_CR36","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2743014","volume":"63","author":"A Je\u017c","year":"2016","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. J. ACM 63(1), 4:1\u20134:51 (2016). https:\/\/doi.org\/10.1145\/2743014","journal-title":"J. ACM"},{"key":"4_CR37","doi-asserted-by":"publisher","unstructured":"Je\u017c, A.: Word equations in nondeterministic linear space. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) ICALP. LIPIcs, vol. 80, pp. 95:1\u201395:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.95","DOI":"10.4230\/LIPIcs.ICALP.2017.95"},{"key":"4_CR38","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.ic.2016.09.007","volume":"251","author":"A Je\u017c","year":"2016","unstructured":"Je\u017c, A., Lohrey, M.: Approximation of smallest linear tree grammar. Inf. Comput. 251, 215\u2013251 (2016). https:\/\/doi.org\/10.1016\/j.ic.2016.09.007","journal-title":"Inf. Comput."},{"key":"4_CR39","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. 7608, pp. 330\u2013335. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34109-0_34"},{"key":"4_CR40","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., Shinohara, A.: Pattern-matching for strings with short descriptions. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol. 937, pp. 205\u2013214. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60044-2_44"},{"key":"4_CR41","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1006\/jabr.1997.7184","volume":"200","author":"O Kharlampovich","year":"1998","unstructured":"Kharlampovich, O., Myasnikov, A.: Irreducible affine varieties over a free group. II: systems in triangular quasi-quadratic form and description of residually free groups. J. Algebra 200, 517\u2013570 (1998)","journal-title":"J. Algebra"},{"key":"4_CR42","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.jalgebra.2006.03.033","volume":"302","author":"O Kharlampovich","year":"2006","unstructured":"Kharlampovich, O., Myasnikov, A.: Elementary theory of free non-abelian groups. J. Algebra 302, 451\u2013552 (2006)","journal-title":"J. Algebra"},{"issue":"4","key":"4_CR43","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1145\/234533.234543","volume":"43","author":"A Ko\u015bcielski","year":"1996","unstructured":"Ko\u015bcielski, A., Pacholski, L.: Complexity of Makanin\u2019s algorithm. J. ACM 43(4), 670\u2013684 (1996). https:\/\/doi.org\/10.1145\/234533.234543","journal-title":"J. ACM"},{"issue":"1\u20132","key":"4_CR44","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0304-3975(96)00321-0","volume":"191","author":"A Ko\u015bcielski","year":"1998","unstructured":"Ko\u015bcielski, A., Pacholski, L.: Makanin\u2019s algorithm is not primitive recursive. Theor. Comput. Sci. 191(1\u20132), 145\u2013156 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(96)00321-0","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"4_CR45","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1142\/S0129054111008088","volume":"22","author":"M Laine","year":"2011","unstructured":"Laine, M., Plandowski, W.: Word equations with one unknown. Int. J. Found. Comput. Sci. 22(2), 345\u2013375 (2011). https:\/\/doi.org\/10.1142\/S0129054111008088","journal-title":"Int. J. Found. Comput. Sci."},{"key":"4_CR46","doi-asserted-by":"publisher","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference, pp. 296\u2013305 (1999). https:\/\/doi.org\/10.1109\/DCC.1999.755679","DOI":"10.1109\/DCC.1999.755679"},{"key":"4_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/3-540-61464-8_63","volume-title":"Rewriting Techniques and Applications","author":"J Levy","year":"1996","unstructured":"Levy, J.: Linear second-order unification. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol. 1103, pp. 332\u2013346. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61464-8_63"},{"issue":"6","key":"4_CR48","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1093\/jigpal\/jzq010","volume":"19","author":"J Levy","year":"2011","unstructured":"Levy, J., Schmidt-Schau\u00df, M., Villaret, M.: On the complexity of bounded second-order unification and stratified context unification. Log. J. IGPL 19(6), 763\u2013789 (2011). https:\/\/doi.org\/10.1093\/jigpal\/jzq010","journal-title":"Log. J. IGPL"},{"issue":"1\u20132","key":"4_CR49","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1006\/inco.2000.2877","volume":"159","author":"J Levy","year":"2000","unstructured":"Levy, J., Veanes, M.: On the undecidability of second-order unification. Inf. Comput. 159(1\u20132), 125\u2013150 (2000). https:\/\/doi.org\/10.1006\/inco.2000.2877","journal-title":"Inf. Comput."},{"key":"4_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/10721975_11","volume-title":"Rewriting Techniques and Applications","author":"J Levy","year":"2000","unstructured":"Levy, J., Villaret, M.: Linear second-order unification and context unification with tree-regular constraints. In: Bachmair, L. (ed.) RTA 2000. LNCS, vol. 1833, pp. 156\u2013171. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10721975_11"},{"key":"4_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/3-540-45610-4_23","volume-title":"Rewriting Techniques and Applications","author":"J Levy","year":"2002","unstructured":"Levy, J., Villaret, M.: Currying second-order unification problems. In: Tison, S. (ed.) RTA 2002. LNCS, vol. 2378, pp. 326\u2013339. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45610-4_23"},{"key":"4_CR52","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). https:\/\/doi.org\/10.1007\/978-3-540-73437-6_24"},{"issue":"2","key":"4_CR53","first-page":"241","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"issue":"103","key":"4_CR54","first-page":"147","volume":"2","author":"G Makanin","year":"1977","unstructured":"Makanin, G.: The problem of solvability of equations in a free semigroup. Matematicheskii Sbornik 2(103), 147\u2013236 (1977). (in Russian)","journal-title":"Matematicheskii Sbornik"},{"key":"4_CR55","doi-asserted-by":"crossref","unstructured":"Makanin, G.: Equations in a free group. Izv. Akad. Nauk SSR Ser. Math. 46, 1199\u20131273 (1983). English translation in Math. USSR Izv. 21 (1983)","DOI":"10.1070\/IM1983v021n03ABEH001803"},{"key":"4_CR56","doi-asserted-by":"crossref","unstructured":"Makanin, G.: Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR Ser. Mat. 48, 735\u2013749 (1984). in Russian. English translation. In: Math. USSR Izvestija 25(75\u201388) (1985)","DOI":"10.1070\/IM1985v025n01ABEH001269"},{"key":"4_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-63045-7_25","volume-title":"Logical Foundations of Computer Science","author":"Y Matiyasevich","year":"1997","unstructured":"Matiyasevich, Y.: Some decision problems for traces. In: Adian, S., Nerode, A. (eds.) LFCS 1997. LNCS, vol. 1234, pp. 248\u2013257. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63045-7_25"},{"issue":"2","key":"4_CR58","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). https:\/\/doi.org\/10.1007\/BF02522825","journal-title":"Algorithmica"},{"key":"4_CR59","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: Apostolico, A., Hein, J. (eds.) CPM 1997. LNCS, vol. 1264, pp. 1\u201311. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63220-4_45"},{"key":"4_CR60","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"CG Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: a linear-time algorithm. J. Artif. Intell. Res. (JAIR) 7, 67\u201382 (1997). https:\/\/doi.org\/10.1613\/jair.374","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"4_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/3-540-63104-6_4","volume-title":"Automated Deduction\u2014CADE-14","author":"J Niehren","year":"1997","unstructured":"Niehren, J., Pinkal, M., Ruhrberg, P.: On equality up-to constraints over finite trees, context unification, and one-step rewriting. In: McCune, W. (ed.) CADE 1997. LNCS, vol. 1249, pp. 34\u201348. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63104-6_4"},{"key":"4_CR62","doi-asserted-by":"publisher","unstructured":"Niehren, J., Pinkal, M., Ruhrberg, P.: A uniform approach to under specification and parallelism. In: Cohen, P.R., Wahlster, W. (eds.) ACL, pp. 410\u2013417. Morgan Kaufmann Publishers\/ACL (1997). https:\/\/doi.org\/10.3115\/979617.979670","DOI":"10.3115\/979617.979670"},{"key":"4_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms \u2014 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). https:\/\/doi.org\/10.1007\/BFb0049431"},{"key":"4_CR64","doi-asserted-by":"publisher","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in NEXPTIME. In: STOC, pp. 721\u2013725. ACM (1999). https:\/\/doi.org\/10.1145\/301250.301443","DOI":"10.1145\/301250.301443"},{"issue":"3","key":"4_CR65","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/990308.990312","volume":"51","author":"W Plandowski","year":"2004","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J. ACM 51(3), 483\u2013496 (2004). https:\/\/doi.org\/10.1145\/990308.990312","journal-title":"J. ACM"},{"key":"4_CR66","doi-asserted-by":"publisher","unstructured":"Plandowski, W.: An efficient algorithm for solving word equations. In: Kleinberg, J.M. (ed.) STOC, pp. 467\u2013476. ACM (2006). https:\/\/doi.org\/10.1145\/1132516.1132584","DOI":"10.1145\/1132516.1132584"},{"key":"4_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/BFb0055097","volume-title":"Automata, Languages and Programming","author":"W Plandowski","year":"1998","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of word equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 731\u2013742. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0055097"},{"key":"4_CR68","unstructured":"Razborov, A.A.: On systems of equations in free groups. Ph.D. thesis, Steklov Institute of Mathematics (1987). (in Russian)"},{"issue":"1","key":"4_CR69","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"JA Robinson","year":"1965","unstructured":"Robinson, J.A.: A machine-oriented logic based on the resolution principle. J. ACM 12(1), 23\u201341 (1965)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"4_CR70","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. 302(1\u20133), 211\u2013222 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00777-6","journal-title":"Theor. Comput. Sci."},{"key":"4_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/978-3-642-02737-6_36","volume-title":"Developments in Language Theory","author":"A Saarela","year":"2009","unstructured":"Saarela, A.: On the complexity of Hmelevskii\u2019s theorem and satisfiability of three unknown equations. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 443\u2013453. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02737-6_36"},{"key":"4_CR72","doi-asserted-by":"publisher","unstructured":"Sahinalp, S.C., Vishkin, U.: Symmetry breaking for suffix tree construction. In: Leighton, F.T., Goodrich, M.T. (eds.) SODA, pp. 300\u2013309. ACM (1994). https:\/\/doi.org\/10.1145\/195058.195164","DOI":"10.1145\/195058.195164"},{"issue":"2\u20134","key":"4_CR73","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 3(2\u20134), 416\u2013430 (2005). https:\/\/doi.org\/10.1016\/j.jda.2004.08.016","journal-title":"J. Discrete Algorithms"},{"key":"4_CR74","unstructured":"Schmidt-Schau\u00df, M.: Unification of stratified second-order terms (1994). Internal Report 12\/94, Johann-Wolfgang-Goethe-Universit\u00e4t"},{"issue":"6","key":"4_CR75","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1093\/logcom\/12.6.929","volume":"12","author":"M Schmidt-Schau\u00df","year":"2002","unstructured":"Schmidt-Schau\u00df, M.: A decision algorithm for stratified context unification. J. Log. Comput. 12(6), 929\u2013953 (2002). https:\/\/doi.org\/10.1093\/logcom\/12.6.929","journal-title":"J. Log. Comput."},{"issue":"2","key":"4_CR76","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2003.08.002","volume":"188","author":"M Schmidt-Schau\u00df","year":"2004","unstructured":"Schmidt-Schau\u00df, M.: Decidability of bounded second order unification. Inf. Comput. 188(2), 143\u2013178 (2004). https:\/\/doi.org\/10.1016\/j.ic.2003.08.002","journal-title":"Inf. Comput."},{"key":"4_CR77","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BFb0052361","volume-title":"Rewriting Techniques and Applications","author":"M Schmidt-Schau\u00df","year":"1998","unstructured":"Schmidt-Schau\u00df, M., Schulz, K.U.: On the exponent of periodicity of minimal solutions of context equations. In: Nipkow, T. (ed.) RTA 1998. LNCS, vol. 1379, pp. 61\u201375. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0052361"},{"issue":"1","key":"4_CR78","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1006\/jsco.2001.0438","volume":"33","author":"M Schmidt-Schau\u00df","year":"2002","unstructured":"Schmidt-Schau\u00df, M., Schulz, K.U.: Solvability of context equations with two context variables is decidable. J. Symb. Comput. 33(1), 77\u2013122 (2002). https:\/\/doi.org\/10.1006\/jsco.2001.0438","journal-title":"J. Symb. Comput."},{"key":"4_CR79","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-55124-7_4","volume-title":"Word Equations and Related Topics","author":"KU Schulz","year":"1992","unstructured":"Schulz, K.U.: Makanin\u2019s algorithm for word equations-two improvements and a generalization. In: Schulz, K.U. (ed.) IWWERT 1990. LNCS, vol. 572, pp. 85\u2013150. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/3-540-55124-7_4"},{"key":"4_CR80","doi-asserted-by":"crossref","unstructured":"Storer, J.A., Szymanski, T.G.: The macro model for data compression. In: STOC, pp. 30\u201339 (1978)","DOI":"10.1145\/800133.804329"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-40608-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T20:42:37Z","timestamp":1741466557000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-40608-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030406073","9783030406080"],"references-count":80,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-40608-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Language and Automata Theory and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lata2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/lata2020.irdta.eu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"In addition, there are 6 invited papers. Due to the coronavirus pandemic the actual conference was postponed to be held together with LATA 2021.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}