{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:17Z","timestamp":1760202677964},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,11]],"date-time":"2014-09-11T00:00:00Z","timestamp":1410393600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9931-3","type":"journal-article","created":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T03:32:26Z","timestamp":1410319946000},"page":"1-48","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["One-Variable Word Equations in Linear Time"],"prefix":"10.1007","volume":"74","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,11]]},"reference":[{"issue":"2","key":"9931_CR1","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput. 22(2), 221\u2013242 (1993). doi: 10.1137\/0222017","journal-title":"SIAM J. Comput."},{"key":"9931_CR2","doi-asserted-by":"crossref","unstructured":"Charatonik, W., Pacholski, L.: Word equations with two variables. In: Abdulrab, H., P\u00e9cuchet, J.P. (eds.) IWWERT, LNCS, vol. 677, pp. 43\u201356. Springer, Berlin (1991). doi: 10.1007\/3-540-56730-5_30","DOI":"10.1007\/3-540-56730-5_30"},{"key":"9931_CR3","doi-asserted-by":"crossref","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, LNCS, vol. 3142, pp. 408\u2013419. Springer, Berlin (2004). doi: 10.1007\/978-3-540-27836-8_36","DOI":"10.1007\/978-3-540-27836-8_36"},{"issue":"4","key":"9931_CR4","doi-asserted-by":"crossref","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 60(4), 819\u2013828 (2011). doi: 10.1007\/s00453-009-9375-3","journal-title":"Algorithmica"},{"key":"9931_CR5","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: Faster fully compressed pattern matching by recompression. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP (1), LNCS, vol. 7391, pp. 533\u2013544. Springer, Berlin (2012). doi: 10.1007\/978-3-642-31594-7_45 . Full version accepted for publication in Transactions on Algorithms. doi: 10.1145\/2631920","DOI":"10.1007\/978-3-642-31594-7_45"},{"key":"9931_CR6","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: Approximation of grammar-based compression via recompression. In: Fischer, J., Sanders, P. (eds.) CPM, LNCS, vol. 7922, pp. 165\u2013176. Springer, Berlin (2013). doi: 10.1007\/978-3-642-38905-4_17 . Full version at http:\/\/arxiv.org\/abs\/1301.5842","DOI":"10.1007\/978-3-642-38905-4_17"},{"key":"9931_CR7","first-page":"233","volume-title":"STACS, LIPIcs","author":"A Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Recompression: a simple and powerful technique for word equations. In: Portier, N., Wilke, T. (eds.) STACS, LIPIcs, vol. 20, pp. 233\u2013244. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2013). doi: 10.4230\/LIPIcs.STACS.2013.233"},{"key":"9931_CR8","doi-asserted-by":"crossref","unstructured":"Je\u017c, A.: The complexity of compressed membership problems for finite automata. Theory of Comput. Syst. (2014). doi: 10.1007\/s00224-013-9443-6","DOI":"10.1007\/s00224-013-9443-6"},{"key":"9931_CR9","unstructured":"Je\u017c, A.: Context unification is in PSPACE. In: ICALP, LNCS, vol. 8573, pp. 244\u2013255. Springer, Berlin (2014). Full version at http:\/\/arxiv.org\/abs\/1310.4367"},{"key":"9931_CR10","unstructured":"Je\u017c, A., Lohrey, M.: Approximation of smallest linear tree grammar. In: Mayr, E.W., Portier, N. (eds.) STACS 2014, LIPIcs, vol. 25, pp. 445\u2013457. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)"},{"issue":"6","key":"9931_CR11","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. JACM 53(6), 918\u2013936 (2006). doi: 10.1145\/1217856.1217858","journal-title":"JACM"},{"key":"9931_CR12","doi-asserted-by":"crossref","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A., Landau, G.M. (eds.) CPM, LNCS, vol. 2089, pp. 181\u2013192. Springer, Berlin (2001). doi: 10.1007\/3-540-48194-X_17","DOI":"10.1007\/3-540-48194-X_17"},{"issue":"2","key":"9931_CR13","doi-asserted-by":"crossref","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). doi: 10.1142\/S0129054111008088","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9931_CR14","doi-asserted-by":"crossref","unstructured":"Lohrey, M., Mathissen, C.: Compressed membership in automata with compressed labels. In: Kulikov, A.S., Vereshchagin, N.K. (eds.) CSR, LNCS, vol. 6651, pp. 275\u2013288. Springer, Berlin (2011). doi: 10.1007\/978-3-642-20712-9_21","DOI":"10.1007\/978-3-642-20712-9_21"},{"key":"9931_CR15","doi-asserted-by":"crossref","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Matematicheskii Sbornik 2(103), 147\u2013236 (1977) (in Russian)","DOI":"10.1070\/SM1977v032n02ABEH002376"},{"issue":"2","key":"9931_CR16","doi-asserted-by":"crossref","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). doi: 10.1007\/BF02522825","journal-title":"Algorithmica"},{"key":"9931_CR17","doi-asserted-by":"crossref","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, LNCS, vol. 841, pp. 336\u2013341. Springer, Berlin (1994). doi: 10.1007\/3-540-58338-6_80","DOI":"10.1007\/3-540-58338-6_80"},{"key":"9931_CR18","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in NEXPTIME. In: STOC, pp. 721\u2013725. ACM (1999). doi: 10.1145\/301250.301443","DOI":"10.1145\/301250.301443"},{"issue":"3","key":"9931_CR19","doi-asserted-by":"crossref","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. JACM 51(3), 483\u2013496 (2004). doi: 10.1145\/990308.990312","journal-title":"JACM"},{"key":"9931_CR20","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","DOI":"10.1145\/1132516.1132584"},{"key":"9931_CR21","first-page":"731","volume-title":"ICALP, LNCS","author":"W Plandowski","year":"1998","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel\u2013Ziv encodings to the solution of word equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP, LNCS, vol. 1443, pp. 731\u2013742. Springer, Berlin (1998). doi: 10.1007\/BFb0055097"},{"issue":"2\u20134","key":"9931_CR22","doi-asserted-by":"crossref","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). doi: 10.1016\/j.jda.2004.08.016","journal-title":"J. Discrete Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9931-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9931-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9931-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T14:15:48Z","timestamp":1551190548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9931-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,11]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9931"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9931-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,11]]}}}