{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:21Z","timestamp":1794381081705,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_36","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"408-419","source":"Crossref","is-referenced-by-count":8,"title":["Solving Two-Variable Word Equations"],"prefix":"10.1007","author":[{"given":"Robert","family":"Da\u0327browski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojtek","family":"Plandowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Finding pattern common to a set of string. In: Proc. STOC 1979, pp. 130\u2013141 (1979)","DOI":"10.1145\/800135.804406"},{"key":"36_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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 in two variables. In: Abdulrab, H., Pecuchet, J.-P. (eds.) IWWERT 1991. LNCS, vol.\u00a0677, pp. 43\u201357. Springer, Heidelberg (1993)"},{"key":"36_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-45687-2_17","volume-title":"Mathematical Foundations of Computer Science 2002","author":"R. Da\u0327browski","year":"2002","unstructured":"Da\u0327browski, R., Plandowski, W.: On word equations in one variable. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 212\u2013221. Springer, Heidelberg (2002)"},{"key":"36_CR4","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, Oxford (1994)"},{"key":"36_CR5","volume-title":"Algebraic Combinatorics on Words","author":"V. Diekert","year":"2002","unstructured":"Diekert, V.: Makanin\u2019s algorithm. In: Lothaire, M. (ed.) Algebraic Combinatorics on Words, vol.\u00a0ch. 13, Cambridge University Press, Cambridge (2002)"},{"key":"36_CR6","volume-title":"Proc. FOCS 1998","author":"C. Gutierrez","year":"1998","unstructured":"Gutierrez, C.: Satisfiability of word equations with constants is in exponential space. In: Proc. FOCS 1998, IEEE Computer Society Press, Palo Alto (1998)"},{"key":"36_CR7","unstructured":"Hmielevskii, Y.I.: Equations in free semigroups. Proc. Steklov Institute of Mathematics, Amer. Math. So., 107 (1976)"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1051\/ita:2000126","volume":"34","author":"L. Ilie","year":"2000","unstructured":"Ilie, L., Plandowski, W.: Two-variable word equations. RAIRO Theoretical Informatics and Applications\u00a034, 467\u2013501 (2000)","journal-title":"RAIRO Theoretical Informatics and Applications"},{"issue":"1","key":"36_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/78935.78938","volume":"37","author":"J. Jaffar","year":"1990","unstructured":"Jaffar, J.: Minimal and complete word unification. Journal of the ACM\u00a037(1), 47\u201385 (1990)","journal-title":"Journal of the ACM"},{"issue":"5","key":"36_CR10","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/337244.337255","volume":"47","author":"J. Karhum\u00e4ki","year":"2000","unstructured":"Karhum\u00e4ki, J., Mignosi, G., Plandowski, W.: The expressibility of languages and relations by word equations. Journal of the ACM\u00a047(5), 483\u2013505 (2000)","journal-title":"Journal of the ACM"},{"issue":"4","key":"36_CR11","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1145\/234533.234543","volume":"43","author":"A. Koscielski","year":"1996","unstructured":"Koscielski, A., Pacholski, L.: Complexity of Makanin\u2019s Algorithm. Journal of the ACM\u00a043(4), 670\u2013684 (1996)","journal-title":"Journal of the ACM"},{"issue":"1-2","key":"36_CR12","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0304-3975(96)00321-0","volume":"191","author":"A. Koscielski","year":"1998","unstructured":"Koscielski, A., Pacholski, L.: Makanin\u2019s algorithm is not primitive recursive. Theoretical Computer Science\u00a0191(1-2), 145\u2013156 (1998)","journal-title":"Theoretical Computer Science"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Mat. Sb.\u00a0103(2), 147\u2013236 (in Russian); English translation in: Math. USSR Sbornik 32, 129\u2013198 (1977)","DOI":"10.1070\/SM1977v032n02ABEH002376"},{"key":"36_CR14","doi-asserted-by":"crossref","first-page":"253","DOI":"10.36045\/bbms\/1103408549","volume":"1","author":"J. Neraud","year":"1994","unstructured":"Neraud, J.: Equations in words: an algorithmic contribution. Bull. Belg. Math. Soc.\u00a01, 253\u2013283 (1994)","journal-title":"Bull. Belg. Math. Soc."},{"key":"36_CR15","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 word equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 731\u2013742. Springer, Heidelberg (1998)"},{"key":"36_CR16","first-page":"721","volume-title":"Proc. STOC 1999","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in NEXPTIME. In: Proc. STOC 1999, pp. 721\u2013725. ACM Press, New York (1999)"},{"key":"36_CR17","first-page":"495","volume-title":"Proc. FOCS 1999","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. In: Proc. FOCS 1999, pp. 495\u2013500. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"36_CR18","first-page":"779","volume":"48","author":"A.A. Razborov","year":"1984","unstructured":"Razborov, A.A.: On systems of equations in a free group. Izv. Akad. Nauk SSSR, Ser. Mat.\u00a048, 779\u2013832 (1984) (in Russian); English translation in Math. USSR Izvestija 25, 115\u2013162 (1985)","journal-title":"Izv. Akad. Nauk SSSR, Ser. Mat."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:30:57Z","timestamp":1619998257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_36","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}