{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:04:42Z","timestamp":1740096282303,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387708"},{"type":"electronic","value":"9783642387715"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38771-5_2","type":"book-chapter","created":{"date-parts":[[2013,6,9]],"date-time":"2013-06-09T22:16:25Z","timestamp":1370816185000},"page":"12-26","source":"Crossref","is-referenced-by-count":3,"title":["Recompression: Word Equations and Beyond"],"prefix":"10.1007","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-56730-5_30","volume-title":"Word Equations and Related Topics","author":"W. Charatonik","year":"1993","unstructured":"Charatonik, W., Pacholski, L.: Word equations with two variables. In: Abdulrab, H., P\u00e9cuchet, J.P. (eds.) IWWERT 1991. LNCS, vol.\u00a0677, pp. 43\u201356. Springer, Heidelberg (1993)"},{"key":"2_CR2","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. D\u0105browski","year":"2004","unstructured":"D\u0105browski, 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.\u00a03142, pp. 408\u2013419. Springer, Heidelberg (2004)"},{"issue":"4","key":"2_CR3","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s00453-009-9375-3","volume":"60","author":"R. D\u0105browski","year":"2011","unstructured":"D\u0105browski, R., Plandowski, W.: On word equations in one variable. Algorithmica\u00a060(4), 819\u2013828 (2011)","journal-title":"Algorithmica"},{"key":"2_CR4","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.\u00a07391, pp. 533\u2013544. Springer, Heidelberg (2012)"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-642-38905-4_17","volume-title":"CPM 2013","author":"A. Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Approximation of grammar-based compression via recompression. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol.\u00a07922, pp. 165\u2013176. Springer, Heidelberg (2013)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: The complexity of compressed membership problems for finite automata. Theory of Computing Systems, 1\u201334 (2013), \n                    \n                      http:\/\/dx.doi.org\/10.1007\/s00224-013-9443-6","DOI":"10.1007\/s00224-013-9443-6"},{"key":"2_CR7","unstructured":"Je\u017c, A.: One-variable word equations in linear time. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS. Springer, Heidelberg (to appear, 2013)"},{"issue":"4","key":"2_CR8","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\u00a043(4), 670\u2013684 (1996)","journal-title":"J. ACM"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference, pp. 296\u2013305. IEEE Computer Society (1999)","DOI":"10.1109\/DCC.1999.755679"},{"key":"2_CR10","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.\u00a04580, pp. 228\u2013240. Springer, Heidelberg (2007)"},{"issue":"2","key":"2_CR11","doi-asserted-by":"crossref","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 Complexity Cryptology\u00a04(2), 241\u2013299 (2012)","journal-title":"Groups Complexity Cryptology"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-20712-9_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M., Mathissen, C.: Compressed membership in automata with compressed labels. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 275\u2013288. Springer, Heidelberg (2011)"},{"issue":"103","key":"2_CR13","first-page":"147","volume":"2","author":"G.S. Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Matematicheskii Sbornik\u00a02(103), 147\u2013236 (1977) (in Russian)","journal-title":"Matematicheskii Sbornik"},{"issue":"2","key":"2_CR14","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\u00a017(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/3-540-58338-6_80","volume-title":"Mathematical Foundations of Computer Science 1994","author":"S.E. Obono","year":"1994","unstructured":"Obono, S.E., Goralcik, P., Maksimenko, M.N.: Efficient solving of the word equations in one variable. In: Pr\u00edvara, I., Rovan, B., Ruzicka, P. (eds.) MFCS 1994. LNCS, vol.\u00a0841, pp. 336\u2013341. Springer, Heidelberg (1994)"},{"issue":"3","key":"2_CR16","first-page":"483","volume":"51","author":"W. Plandowski","year":"2004","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. J.\u00a0ACM\u00a051(3), 483\u2013496 (2004)","journal-title":"J.\u00a0ACM"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: An efficient algorithm for solving word equations. In: Kleinberg, J.M. (ed.) STOC, pp. 467\u2013476. ACM (2006)","DOI":"10.1145\/1132516.1132584"},{"key":"2_CR18","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 words equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 731\u2013742. Springer, Heidelberg (1998)"},{"issue":"2-4","key":"2_CR19","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\u00a03(2-4), 416\u2013430 (2005)","journal-title":"J. Discrete Algorithms"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38771-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,20]],"date-time":"2019-01-20T10:31:23Z","timestamp":1547980283000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38771-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387708","9783642387715"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38771-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}