{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T21:51:47Z","timestamp":1771883507331,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T00:00:00Z","timestamp":1455235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2011\/01\/D\/ST6\/0716"],"award-info":[{"award-number":["2011\/01\/D\/ST6\/0716"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,3,30]]},"abstract":"<jats:p>\n            In this article, we present an application of a simple technique of local recompression, previously developed by the author in the context algorithms for compressed strings [Je\u017c 2014a, 2015b, 2015a], to word equations. The technique is based on local modification of variables (replacing\n            <jats:italic>X<\/jats:italic>\n            by\n            <jats:italic>aX<\/jats:italic>\n            or\n            <jats:italic>Xa<\/jats:italic>\n            ) and iterative replacement of pairs of letters occurring in the equation by a \u201cfresh\u201d letter, which can be seen as a bottom-up\n            <jats:italic>compression<\/jats:italic>\n            of the solution of the given word equation, or, to be more specific, building a Straight-Line Programme for the solution of the word equation.\n          <\/jats:p>\n          <jats:p>\n            Using this technique, we give new, independent, and self-contained proofs of many known results for word equations. To be more specific, the presented (nondeterministic) algorithm runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            space and in time polynomial in\n            <jats:italic>n<\/jats:italic>\n            and log\n            <jats:italic>N<\/jats:italic>\n            , where\n            <jats:italic>n<\/jats:italic>\n            is the size of the input equation and\n            <jats:italic>N<\/jats:italic>\n            the size of the length-minimal solution of the word equation. Furthermore, for\n            <jats:italic>O<\/jats:italic>\n            (1) variables, the bound on the space consumption is in fact linear, that is,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ), where\n            <jats:italic>m<\/jats:italic>\n            is the size of the space used by the input. This yields that for each\n            <jats:italic>k<\/jats:italic>\n            the set of satisfiable word equations with\n            <jats:italic>k<\/jats:italic>\n            variables is context sensitive. The presented algorithm can be easily generalised to a generator of all solutions of the given word equation (without increasing the space usage). Furthermore, a further analysis of the algorithm yields an independent proof of doubly exponential upper bound on the size of the length-minimal solution. The presented algorithm does not use exponential bound on the exponent of periodicity. Conversely, the analysis of the algorithm yields an independent proof of the exponential bound on exponent of periodicity.\n          <\/jats:p>","DOI":"10.1145\/2743014","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T13:07:16Z","timestamp":1456146436000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":48,"title":["Recompression"],"prefix":"10.1145","volume":"63","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2016,2,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Stephen Alstrup Gerth S. Brodal and Theis Rauhe. 2000. Pattern matching in dynamic texts. In SODA David B. Shmoys (Ed.). ACM\/SIAM 819--828. DOI:http:\/\/dx.doi.org\/doi.acm.org\/10.1145\/338219.338645   Stephen Alstrup Gerth S. Brodal and Theis Rauhe. 2000. Pattern matching in dynamic texts. In SODA David B. Shmoys (Ed.). ACM\/SIAM 819--828. DOI:http:\/\/dx.doi.org\/doi.acm.org\/10.1145\/338219.338645"},{"key":"e_1_2_1_2_1","volume-title":"CSR (LNCS), Edward A","author":"Diekert Volker"},{"key":"e_1_2_1_3_1","volume-title":"ICALP (LNCS), Josep D\u00edaz, Juhani Karhum\u00e4ki, Arto Lepist\u00f6","author":"D\u0105browski Robert"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9375-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1978-0500555-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Claudio Guti\u00e9rrez. 1998. Satisfiability of word equations with constants is in exponential space. In FOCS. IEEE Computer Society 112--119. DOI:http:\/\/dx.doi.org\/10.1109\/SFCS.1998.743434   Claudio Guti\u00e9rrez. 1998. Satisfiability of word equations with constants is in exponential space. In FOCS. IEEE Computer Society 112--119. DOI:http:\/\/dx.doi.org\/10.1109\/SFCS.1998.743434","DOI":"10.1109\/SFCS.1998.743434"},{"key":"e_1_2_1_7_1","first-page":"467","article-title":"Two-variable word equations","volume":"34","author":"Ilie Lucian","year":"2000","journal-title":"ITA"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/78935.78938"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9443-6"},{"key":"e_1_2_1_10_1","volume-title":"ICALP (LNCS)","author":"Je\u017c Artur"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.027"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2631920"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.032"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9931-3"},{"key":"e_1_2_1_15_1","volume-title":"Ernst W. Mayr and Natacha Portier (Eds.)","volume":"25","author":"Je\u017c Artur","year":"2014"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234543"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008088"},{"key":"e_1_2_1_18_1","first-page":"39","article-title":"Une borne pour les g\u00e9n\u00e9rateurs des solutions enti\u00e8res positives d\u2019une \u00e9quation diophantienne lin\u00e9aire","volume":"305","author":"Lambert J. L.","year":"1987","journal-title":"C.-R. Acad. Sci. Paris"},{"key":"e_1_2_1_19_1","volume-title":"Data Compression Conference. IEEE Computer Society","author":"Jesper Larsson N.","year":"1999"},{"key":"e_1_2_1_20_1","volume-title":"CSR (LNCS), Alexander S","author":"Lohrey Markus"},{"key":"e_1_2_1_21_1","first-page":"147","article-title":"The problem of solvability of equations in a free semigroup","volume":"2","author":"Makanin Gennadi\u00ed","year":"1977","journal-title":"Mat. Sbornik"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522825"},{"key":"e_1_2_1_23_1","volume-title":"ESA (LNCS), Jan van Leeuwen (Ed.)","author":"Plandowski Wojciech"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301443"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990312"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132584"},{"key":"e_1_2_1_27_1","unstructured":"Wojciech Plandowski. 2012. Personal communication (2012).  Wojciech Plandowski. 2012. Personal communication (2012)."},{"key":"e_1_2_1_28_1","volume-title":"ICALP (LNCS)","author":"Plandowski Wojciech"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.016"},{"key":"e_1_2_1_30_1","volume-title":"IWWERT (LNCS), Klaus U","author":"Schulz Klaus U."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743014","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2743014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:34Z","timestamp":1750227394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2743014"}},"subtitle":["A Simple and Powerful Technique for Word Equations"],"short-title":[],"issued":{"date-parts":[[2016,2,12]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,3,30]]}},"alternative-id":["10.1145\/2743014"],"URL":"https:\/\/doi.org\/10.1145\/2743014","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,12]]},"assertion":[{"value":"2013-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}