{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T13:51:22Z","timestamp":1710251482488},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,12,2]],"date-time":"2009-12-02T00:00:00Z","timestamp":1259712000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s00453-009-9375-3","type":"journal-article","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T16:19:48Z","timestamp":1259684388000},"page":"819-828","source":"Crossref","is-referenced-by-count":16,"title":["On Word Equations in One Variable"],"prefix":"10.1007","volume":"60","author":[{"given":"Robert","family":"D\u0105browski","sequence":"first","affiliation":[]},{"given":"Wojciech","family":"Plandowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,12,2]]},"reference":[{"key":"9375_CR1","first-page":"130","volume-title":"Proceedings of Symposium on the Theory of Computing","author":"D. Angluin","year":"1979","unstructured":"Angluin, D.: Finding pattern common to a set of string. In: Proceedings of Symposium on the Theory of Computing, STOC\u201979, pp. 130\u2013141. ACM, New York (1979)"},{"key":"9375_CR2","series-title":"Lecture Notes in Computer Science","first-page":"43","volume-title":"Proceedings of the International Workshop on Word Equations and Related Topics","author":"W. Charatonik","year":"1991","unstructured":"Charatonik, W., Pacholski, L.: Word equations in two variables. In: Proceedings of the International Workshop on Word Equations and Related Topics, IWWERT\u201991. Lecture Notes in Computer Science, vol. 677, pp. 43\u201357. Springer, Berlin (1991)"},{"key":"9375_CR3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-1-4613-9323-8_12","volume-title":"Sequences II","author":"M. Crochemore","year":"1993","unstructured":"Crochemore, M., Rytter, W.: Periodic prefixes in texts. In: Capocelli, R., De\u00a0Santis, A., Vaccaro, U. (eds) Sequences II, Positano, 1991, pp. 153\u2013165. Springer, New York (1993)"},{"key":"9375_CR4","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, London (1994)"},{"key":"9375_CR5","first-page":"112","volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science","author":"C. Gutierrez","year":"1998","unstructured":"Gutierrez, C.: Satisfiability of word equations with constants is in exponential space. In: Proceedings of the Annual Symposium on Foundations of Computer Science, FOCS\u201998, pp. 112\u2013119. IEEE Comput. Soc. Press, Los Alamitos (1998)"},{"key":"9375_CR6","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1051\/ita:2000126","volume":"34","author":"L. Ilie","year":"2000","unstructured":"Ilie, L., Plandowski, W.: Two-variable word equations. Theor. Inform. Appl. 34, 467\u2013501 (2000)","journal-title":"Theor. Inform. Appl."},{"issue":"4","key":"9375_CR7","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1145\/234533.234543","volume":"43","author":"A. Ko\u015bcielski","year":"1996","unstructured":"Ko\u015bcielski, A., Pacholski, L.: Complexity of Makanin\u2019s algorithm. J. Assoc. Comput. Math. 43(4), 670\u2013684 (1996)","journal-title":"J. Assoc. Comput. Math."},{"issue":"2","key":"9375_CR8","first-page":"147","volume":"103","author":"G.S. Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Mat. Sb. 103(2), 147\u2013236 (1977) (in Russian). English translation in: Math. USSR Sb. 32, 129\u2013198 (1977)","journal-title":"Mat. Sb."},{"key":"9375_CR9","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. 1, 253\u2013283 (1994)","journal-title":"Bull. Belg. Math. Soc."},{"key":"9375_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/3-540-58338-6_80","volume-title":"Mathematical Foundations of Computer Science 1994","author":"S. Eyono Obono","year":"1994","unstructured":"Eyono Obono, S., Goralcik, P., Maksimenko, M.N.: Efficient solving of the word equations in one variable. In: Mathematical Foundations of Computer Science 1994, 19th International Symposium, MFCS\u201994. Lecture Notes in Computer Science, vol. 841, pp. 336\u2013341. Springer, Berlin (1994)"},{"key":"9375_CR11","first-page":"721","volume-title":"Proceedings of the Symposium on the Theory of Computing","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W.: Satisfiability of word equations is in NEXPTIME. In: Proceedings of the Symposium on the Theory of Computing, STOC\u201999, pp. 721\u2013725. ACM, New York (1999)"},{"key":"9375_CR12","first-page":"495","volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W.: Satisfiability of word equations is in PSPACE. In: Proceedings of the Annual Symposium on Foundations of Computer Science, FOCS\u201999, pp. 495\u2013500. IEEE Comput. Soc., Los Alamitos (1999)"},{"key":"9375_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1007\/BFb0055097","volume-title":"Proceedings of the International Colloquium on 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: Proceedings of the International Colloquium on Automata, Languages and Programming, ICALP\u201998. Lecture Notes in Computer Science, vol. 1443, pp. 731\u2013742. Springer, Berlin (1998)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9375-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9375-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9375-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,24]],"date-time":"2020-05-24T00:28:11Z","timestamp":1590280091000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9375-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,2]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["9375"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9375-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,2]]}}}