{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:19:47Z","timestamp":1775053187962,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642027369","type":"print"},{"value":"9783642027376","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02737-6_36","type":"book-chapter","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T08:40:30Z","timestamp":1246351230000},"page":"443-453","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of Hmelevskii\u2019s Theorem and Satisfiability of Three Unknown Equations"],"prefix":"10.1007","author":[{"given":"Aleksi","family":"Saarela","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0304-3975(85)90066-0","volume":"41","author":"M.H. Albert","year":"1985","unstructured":"Albert, M.H., Lawrence, J.: A proof of Ehrenfeucht\u2019s conjecture. Theoret. Comput. Sci.\u00a041, 121\u2013123 (1985)","journal-title":"Theoret. Comput. Sci."},{"key":"36_CR2","volume-title":"Handbook of Formal Languages","author":"C. Choffrut","year":"1997","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Combinatorics of words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Springer, Heidelberg (1997)"},{"key":"36_CR3","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1142\/S0129054107005030","volume":"18","author":"E. Czeizler","year":"2007","unstructured":"Czeizler, E., Karhum\u00e4ki, J.: On non-periodic solutions of independent systems of word equations over three unknowns. Internat. J. Found. Comput. Sci.\u00a018, 873\u2013897 (2007)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0021-8693(69)90070-2","volume":"13","author":"S. Eilenberg","year":"1969","unstructured":"Eilenberg, S., Sch\u00fctzenberger, M.P.: Rational sets in commutative monoids. J. Algebra\u00a013, 173\u2013191 (1969)","journal-title":"J. Algebra"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1090\/S0002-9939-1978-0500555-0","volume":"72","author":"J. Gathen von zur","year":"1978","unstructured":"von zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proc. Amer. Math. Soc.\u00a072, 155\u2013158 (1978)","journal-title":"Proc. Amer. Math. Soc."},{"key":"36_CR6","first-page":"321","volume":"40","author":"V.S. Guba","year":"1986","unstructured":"Guba, V.S.: Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems. Mat. Zametki\u00a040, 321\u2013324 (1986)","journal-title":"Mat. Zametki"},{"key":"36_CR7","volume-title":"Algebraic Combinatorics on Words","author":"T. Harju","year":"2002","unstructured":"Harju, T., Karhum\u00e4ki, J., Plandowski, W.: Independent systems of equations. In: Lothaire, M. (ed.) Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)"},{"key":"#cr-split#-36_CR8.1","unstructured":"Hmelevskii, Y.I.: Equations in free semigroups. Proc. Steklov Inst. of Math. 107 (1971);"},{"key":"#cr-split#-36_CR8.2","unstructured":"Amer. Math. Soc. Translations (1976)"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Karhum\u00e4ki, J., Saarela, A.: An analysis and a reproof of Hmelevskii\u2019s theorem. In: Proc. of 12th International Conference on Developments in Language Theory, pp. 467\u2013478 (2008)","DOI":"10.1007\/978-3-540-85780-8_37"},{"key":"36_CR10","volume-title":"Combinatorics on words","author":"M. Lothaire","year":"1983","unstructured":"Lothaire, M.: Combinatorics on words. Addison-Wesley, Reading (1983)"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Mat. Sb. 103, 147\u2013236; English transl. in Math. USSR Sb. 32, 129\u2013198 (1977)","DOI":"10.1070\/SM1977v032n02ABEH002376"},{"key":"36_CR12","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\u00a051, 483\u2013496 (2004)","journal-title":"J. ACM"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of word equations. In: Proc. of 25th International Colloquium on Automata, Languages, and Programming, pp. 731\u2013742 (1998)","DOI":"10.1007\/BFb0055097"},{"key":"36_CR14","unstructured":"Saarela, A.: A new proof of Hmelevskii\u2019s theorem. Licentiate thesis, Univ. Turku (2009), http:\/\/users.utu.fi\/amsaar\/en\/licthesis.pdf"},{"key":"36_CR15","unstructured":"Spehner, J.-C.: Quelques problemes d\u2019extension, de conjugaison et de presentation des sous-monoides d\u2019un monoide libre. Ph.D. Thesis, Univ. Paris (1976)"},{"key":"36_CR16","doi-asserted-by":"crossref","unstructured":"Spehner, J.-C.: Les presentations des sous-monoides de rang 3 d\u2019un monoide libre. Semigroups. In: Proc. Conf. Math. Res. Inst., pp. 116\u2013155 (1978)","DOI":"10.1007\/BFb0089813"}],"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-02737-6_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:25:17Z","timestamp":1558398317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02737-6_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642027369","9783642027376"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02737-6_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}