{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:07Z","timestamp":1760202667861},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319066851"},{"type":"electronic","value":"9783319066868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_1","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T05:30:40Z","timestamp":1401687040000},"page":"1-15","source":"Crossref","is-referenced-by-count":1,"title":["Finding All Solutions of Equations in Free Groups and Monoids with Involution"],"prefix":"10.1007","author":[{"given":"Volker","family":"Diekert","sequence":"first","affiliation":[]},{"given":"Artur","family":"Je\u017c","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Plandowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","first-page":"1188","volume":"269","author":"M. Benois","year":"1969","unstructured":"Benois, M.: Parties rationelles du groupe libre. C. R. Acad. Sci. Paris, S\u00e9r. A\u00a0269, 1188\u20131190 (1969)","journal-title":"C. R. Acad. Sci. Paris, S\u00e9r. A"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1112\/jtopol\/jtq010","volume":"3","author":"F. Dahmani","year":"2010","unstructured":"Dahmani, F., Guirardel, V.: Foliations for solving equations in groups: free, virtually free and hyperbolic groups. J. of Topology\u00a03, 343\u2013404 (2010)","journal-title":"J. of Topology"},{"key":"#cr-split#-1_CR3.1","doi-asserted-by":"crossref","unstructured":"Diekert, V., Guti\u00e9rrez, C., Hagenah, C.: The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inf. and Comput.\u00a0202, 105-140 (2005)","DOI":"10.1016\/j.ic.2005.04.002"},{"key":"#cr-split#-1_CR3.2","unstructured":"Conference version in Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 170-182. Springer, Heidelberg (2001)"},{"issue":"3","key":"1_CR4","first-page":"493","volume":"18","author":"V. Diekert","year":"2008","unstructured":"Diekert, V., Lohrey, M.: Word equations over graph products. IJAC\u00a018(3), 493\u2013533 (2008)","journal-title":"IJAC"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Diekert, V., Matiyasevich, Y., Muscholl, A.: Solving word equations modulo partial commutations. TCS 224, 215\u2013235 (1999); Special issue of LFCS 1997","DOI":"10.1016\/S0304-3975(98)00313-2"},{"key":"#cr-split#-1_CR6.1","doi-asserted-by":"crossref","unstructured":"Diekert, V., Muscholl, A.: Solvability of equations in free partially commutative groups is decidable. International Journal of Algebra and Computation\u00a016, 1047-1070 (2006)","DOI":"10.1142\/S0218196706003372"},{"key":"#cr-split#-1_CR6.2","unstructured":"Journal version of Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 543-554. Springer, Heidelberg (2001)"},{"key":"#cr-split#-1_CR7.1","doi-asserted-by":"crossref","unstructured":"Durnev, V.G.: Undecidability of the positive \u2200\u2009\u2203\u20093-theory of a free semi-group. Sibirsky Matematicheskie Jurnal\u00a036(5), 1067-1080 (1995) (in Russian)","DOI":"10.1007\/BF02112533"},{"key":"#cr-split#-1_CR7.2","unstructured":"English translation: Sib. Math. J. 36(5), 917-929 (1995)"},{"key":"1_CR8","volume-title":"Automata, Languages, and Machines","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol.\u00a0A. Academic Press, New York (1974)"},{"key":"1_CR9","first-page":"112","volume-title":"Proc. 39th FOCS 1998","author":"C. Guti\u00e9rrez","year":"1998","unstructured":"Guti\u00e9rrez, C.: Satisfiability of word equations with constants is in exponential space. In: Proc. 39th FOCS 1998, pp. 112\u2013119. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Guti\u00e9rrez, C.: Satisfiability of equations in free groups is in PSPACE. In: Proc. 32nd STOC 2000, pp. 21\u201327. ACM Press (2000)","DOI":"10.1145\/335305.335308"},{"key":"1_CR11","unstructured":"Hopcroft, J.E., Ulman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)"},{"key":"1_CR12","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. Theoretical Informatics and Applications\u00a034, 467\u2013501 (2000)","journal-title":"Theoretical Informatics and Applications"},{"key":"1_CR13","series-title":"LIPIcs","first-page":"233","volume-title":"STACS","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.\u00a020, pp. 233\u2013244. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2013)"},{"issue":"2","key":"1_CR14","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1006\/jabr.1997.7184","volume":"200","author":"O. Kharlampovich","year":"1998","unstructured":"Kharlampovich, O., Myasnikov, A.: Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups. J. of Algebra\u00a0200(2), 517\u2013570 (1998)","journal-title":"J. of Algebra"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.jalgebra.2006.03.033","volume":"302","author":"O. Kharlampovich","year":"2006","unstructured":"Kharlampovich, O., Myasnikov, A.: Elementary theory of free non-abelian groups. J. of Algebra\u00a0302, 451\u2013552 (2006)","journal-title":"J. of Algebra"},{"issue":"4","key":"1_CR16","doi-asserted-by":"publisher","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. Association for Computing Machinery\u00a043(4), 670\u2013684 (1996)","journal-title":"J. Association for Computing Machinery"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Math. Sbornik\u00a0103, 147\u2013236 (1977) English transl. in Math. USSR Sbornik 32 (1977)","DOI":"10.1070\/SM1977v032n02ABEH002376"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Makanin, G.S.: Equations in a free group. Izv. Akad. Nauk SSR, Ser. Math.\u00a046, 1199\u20131273 (1983) English transl. in Math. USSR Izv. 21 (1983)","DOI":"10.1070\/IM1983v021n03ABEH001803"},{"key":"#cr-split#-1_CR19.1","unstructured":"Makanin, G.S.: Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR, Ser. Mat.\u00a048, 735-749 (1984) (in Russian)"},{"key":"#cr-split#-1_CR19.2","unstructured":"English translation in: Math.\u00a0USSR Izvestija 25, 75-88 (1985)"},{"key":"1_CR20","volume-title":"Hilbert\u2019s Tenth Problem","author":"Y. Matiyasevich","year":"1993","unstructured":"Matiyasevich, Y.: Hilbert\u2019s Tenth Problem. MIT Press, Cambridge (1993)"},{"key":"1_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-63045-7_25","volume-title":"Logical Foundations of Computer Science","author":"Y. Matiyasevich","year":"1997","unstructured":"Matiyasevich, Y.: Some decision problems for traces. In: Adian, S., Nerode, A. (eds.) LFCS 1997. LNCS, vol.\u00a01234, pp. 248\u2013257. Springer, Heidelberg (1997)"},{"key":"1_CR22","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. Association for Computing Machinery\u00a051, 483\u2013496 (2004)","journal-title":"J. Association for Computing Machinery"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: An efficient algorithm for solving word equations. In: Proc. 38th STOC 2006, pp. 467\u2013476. ACM Press (2006)","DOI":"10.1145\/1132516.1132584"},{"key":"1_CR24","unstructured":"Plandowski, W.: (unpublished, 2014)"},{"key":"1_CR25","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":"1_CR26","unstructured":"Razborov, A.A.: On Systems of Equations in Free Groups. PhD thesis, Steklov Institute of Mathematics (1987) (in Russian)"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: On systems of equations in free groups. In: Combinatorial and Geometric Group Theory, pp. 269\u2013283. Cambridge University Press (1994)","DOI":"10.1017\/CBO9780511566073.022"},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01241140","volume":"120","author":"E. Rips","year":"1995","unstructured":"Rips, E., Sela, Z.: Canonical representatives and equations in hyperbolic groups. Inventiones Mathematicae\u00a0120, 489\u2013512 (1995)","journal-title":"Inventiones Mathematicae"},{"key":"1_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-55124-7_4","volume-title":"Word Equations and Related Topics","author":"K.U. Schulz","year":"1992","unstructured":"Schulz, K.U.: Makanin\u2019s algorithm for word equations \u2014 Two improvements and a generalization. In: Schulz, K.U. (ed.) IWWERT 1990. LNCS, vol.\u00a0572, pp. 85\u2013150. Springer, Heidelberg (1992)"}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T00:09:50Z","timestamp":1558915790000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}