{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:12Z","timestamp":1740109392478,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T00:00:00Z","timestamp":1724112000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T00:00:00Z","timestamp":1724112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005609","name":"University of Turku","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005609","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It is known that the set of solutions of any constant-free three-variable word equation can be represented using parametric words, and the number of numerical parameters and the level of nesting in these parametric words is at most logarithmic with respect to the length of the equation. We show that this result can be significantly improved in the case of unbalanced equations, that is, equations where at least one variable has a different number of occurrences on the left-hand side and on the right-hand side. More specifically, it is sufficient to have two numerical parameters and one level of nesting in this case. We also discuss the possibility of proving a similar result for balanced equations in the future.<\/jats:p>","DOI":"10.1007\/s00224-024-10193-9","type":"journal-article","created":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T05:01:56Z","timestamp":1724130116000},"page":"1556-1571","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Solution Sets of Three-Variable Word Equations"],"prefix":"10.1007","volume":"68","author":[{"given":"Aleksi","family":"Saarela","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,20]]},"reference":[{"key":"10193_CR1","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jcss.2021.08.001","volume":"123","author":"A Je\u017c","year":"2022","unstructured":"Je\u017c, A.: Word equations in non-deterministic linear space. J. Comput. Syst. Sci. 123, 122\u2013142 (2022). https:\/\/doi.org\/10.1016\/j.jcss.2021.08.001","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10193_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0304-3975(85)90066-0","volume":"41","author":"MH Albert","year":"1985","unstructured":"Albert, M.H., Lawrence, J.: A proof of Ehrenfeucht\u2019s conjecture. Theoret. Comput. Sci. 41(1), 121\u2013123 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90066-0","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10193_CR3","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF01142470","volume":"40","author":"VS Guba","year":"1986","unstructured":"Guba, V.S.: Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems. Matematicheskie Zametki. 40(3), 321\u2013324 (1986). https:\/\/doi.org\/10.1007\/BF01142470","journal-title":"Matematicheskie Zametki."},{"key":"10193_CR4","doi-asserted-by":"publisher","unstructured":"Saarela, A.: Hardness results for constant-free pattern languages and word equations. In: Proceedings of the 47th ICALP, LIPIcs, vol. 168 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020), pp. 140:1\u2013140:15. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.140","DOI":"10.4230\/LIPIcs.ICALP.2020.140"},{"key":"10193_CR5","unstructured":"Hmelevski\u012d, J.I.: Equations in free semigroups (American Mathematical Society, 1976). Translated by G. A. Kandall from the Russian original: Trudy Mat. Inst. Steklov. 107 (1971)"},{"issue":"1","key":"10193_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/20M1310448","volume":"51","author":"D Nowotka","year":"2022","unstructured":"Nowotka, D., Saarela, A.: An optimal bound on the solution sets of one-variable word equations and its consequences. SIAM J. Comput. 51(1), 1\u201318 (2022). https:\/\/doi.org\/10.1137\/20M1310448","journal-title":"SIAM J. Comput."},{"key":"10193_CR7","doi-asserted-by":"publisher","unstructured":"Karhum\u00e4ki, J., Saarela, A.: An analysis and a reproof of Hmelevskii\u2019s theorem. In: Proceedings of the 12th DLT, LNCS, vol. 5257 (Springer, 2008), pp. 467\u2013478. https:\/\/doi.org\/10.1007\/978-3-540-85780-8_37","DOI":"10.1007\/978-3-540-85780-8_37"},{"key":"10193_CR8","unstructured":"Saarela, A.: Word equations and related topics: independence, decidability and characterizations (2012). http:\/\/urn.fi\/URN:ISBN:978-952-12-2737-0. Doctoral dissertation, University of Turku"},{"key":"10193_CR9","doi-asserted-by":"publisher","unstructured":"Saarela, A.: On the complexity of Hmelevskii\u2019s theorem and satisfiability of three unknown equations. In: Proceedings of the 13th DLT, LNCS, vol. 5583 (Springer, 2009), pp. 443\u2013453. https:\/\/doi.org\/10.1007\/978-3-642-02737-6_36","DOI":"10.1007\/978-3-642-02737-6_36"},{"key":"10193_CR10","doi-asserted-by":"publisher","unstructured":"Saarela, A.: On the solution sets of entire systems of word equations. In: Proceedings of the 14th WORDS, LNCS, vol. 13899 (Springer, 2023), pp. 261\u2013273. https:\/\/doi.org\/10.1007\/978-3-031-33180-0_20","DOI":"10.1007\/978-3-031-33180-0_20"},{"key":"10193_CR11","unstructured":"Lothaire, M.: Combinatorics on Words (Addison-Wesley, 1983)"},{"key":"10193_CR12","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words (Cambridge University Press, 2002). http:\/\/www-igm.univ-mlv.fr\/~berstel\/Lothaire\/AlgCWContents.html","DOI":"10.1017\/CBO9781107326019"},{"key":"10193_CR13","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. Proceedings of the American Mathematical Society. 16, 109\u2013114 (1965). https:\/\/doi.org\/10.1090\/S0002-9939-1965-0174934-9","journal-title":"Proceedings of the American Mathematical Society."},{"issue":"1","key":"10193_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0304-3975(03)00098-7","volume":"307","author":"T Harju","year":"2003","unstructured":"Harju, T., Nowotka, D.: On the independence of equations in three variables. Theoret. Comput. Sci. 307(1), 139\u2013172 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(03)00098-7","journal-title":"Theoret. Comput. Sci."},{"key":"10193_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejc.2015.01.005","volume":"47","author":"A Saarela","year":"2015","unstructured":"Saarela, A.: Systems of word equations, polynomials and linear algebra: a new approach. Eur. J. Comb. 47, 1\u201314 (2015). https:\/\/doi.org\/10.1016\/j.ejc.2015.01.005","journal-title":"Eur. J. Comb."},{"key":"10193_CR16","first-page":"267","volume":"14","author":"LG Budkina","year":"1973","unstructured":"Budkina, L.G., Markov, A.A.: F-semigroups with three generators. Akademiya Nauk SSSR. Matematicheskie Zametki. 14, 267\u2013277 (1973)","journal-title":"Akademiya Nauk SSSR. Matematicheskie Zametki."},{"key":"10193_CR17","unstructured":"Spehner, J.C.: Quelques probl\u00e9mes d\u2019extension, de conjugaison et de pr\u00e9sentation des sous-mono\u00efde d\u2019un mono\u00efde libre. Ph.D. thesis, Univ. Paris (1976)"},{"key":"10193_CR18","doi-asserted-by":"publisher","unstructured":"Spehner, J.C.: Les systemes entiers d\u2019\u00e9quations sur un alphabet de 3 variables, in Semigroups Theory and Applications, LNM, vol. 1320 (Springer, 1988), pp. 342\u2013357. https:\/\/doi.org\/10.1007\/BFb0083443","DOI":"10.1007\/BFb0083443"},{"issue":"5","key":"10193_CR19","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1142\/S0129054118420121","volume":"29","author":"D Nowotka","year":"2018","unstructured":"Nowotka, D., Saarela, A.: One-variable word equations and three-variable constantfree word equations. Int. J. Found. Comput. Sci. 29(5), 935\u2013950 (2018). https:\/\/doi.org\/10.1142\/S0129054118420121","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10193_CR20","doi-asserted-by":"publisher","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","DOI":"10.1142\/S0129054111008088"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10193-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10193-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10193-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T06:02:51Z","timestamp":1734156171000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10193-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,20]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10193"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10193-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,8,20]]},"assertion":[{"value":"5 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}