{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T17:01:16Z","timestamp":1768410076400,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642396106","type":"print"},{"value":"9783642396113","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39611-3_21","type":"book-chapter","created":{"date-parts":[[2013,7,3]],"date-time":"2013-07-03T22:33:07Z","timestamp":1372890787000},"page":"209-226","source":"Crossref","is-referenced-by-count":48,"title":["Word Equations with Length Constraints: What\u2019s Decidable?"],"prefix":"10.1007","author":[{"given":"Vijay","family":"Ganesh","sequence":"first","affiliation":[]},{"given":"Mia","family":"Minnes","sequence":"additional","affiliation":[]},{"given":"Armando","family":"Solar-Lezama","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Rinard","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","unstructured":"Blumensath, A.: Automatic structures. Diploma thesis, RWTH-Aachen (1999)"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Cadar, C., Ganesh, V., Pawlowski, P., Dill, D., Engler, D.: EXE: automatically generating inputs of death. In: Juels, A., Wright, R.N., De Capitani di Vimercati, S. (eds.) ACM Conference on Computer and Communications Security, pp. 322\u2013335. ACM (2006)","DOI":"10.1145\/1180405.1180445"},{"key":"21_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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 with two variables. In: Abdulrab, H., P\u00e9cuchet, J.-P. (eds.) IWWERT 1991. LNCS, vol.\u00a0677, pp. 43\u201356. Springer, Heidelberg (1993)"},{"issue":"4","key":"21_CR4","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s00453-009-9375-3","volume":"60","author":"R. Dabrowski","year":"2011","unstructured":"Dabrowski, R., Plandowski, W.: On word equations in one variable. Algorithmica\u00a060(4), 819\u2013828 (2011)","journal-title":"Algorithmica"},{"issue":"5","key":"21_CR5","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1007\/BF02112533","volume":"36","author":"V. Durnev","year":"1995","unstructured":"Durnev, V.: Undecidability of the positive \u2200\u2009\u2203\u20093-theory of a free semigroup. Siberian Mathematical Journal\u00a036(5), 1067\u20131080 (1995)","journal-title":"Siberian Mathematical Journal"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Ebbinghaus, H.-D., Flum, J., Thomas, W.: Mathematical Logic. Undergraduate Texts in Mathematics. Springer (1994)","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Emmi, M., Majumdar, R., Sen, K.: Dynamic test input generation for database applications. In: Rosenblum, D., Elbaum, S. (eds.) ISSTA, pp. 151\u2013162. ACM (2007)","DOI":"10.1145\/1273463.1273484"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-22110-1_1","volume-title":"Computer Aided Verification","author":"V. Ganesh","year":"2011","unstructured":"Ganesh, V., Kie\u017cun, A., Artzi, S., Guo, P.J., Hooimeijer, P., Ernst, M.: HAMPI: A string solver for testing, analysis and vulnerability detection. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol.\u00a06806, pp. 1\u201319. Springer, Heidelberg (2011)"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Godefroid, P., Klarlund, N., Sen, K.: DART: directed automated random testing. In: Sarkar, V., Hall, M. (eds.) PLDI, pp. 213\u2013223. ACM (2005)","DOI":"10.1145\/1064978.1065036"},{"key":"21_CR10","unstructured":"Hopcroft, J., Motwani, R., Ullman, J.: Introduction to automata theory, languages, and computation. Pearson\/Addison Wesley (2007)"},{"issue":"6","key":"21_CR11","first-page":"467","volume":"34","author":"L. Ilie","year":"2000","unstructured":"Ilie, L., Plandowski, W.: Two-variable word equations. ITA\u00a034(6), 467\u2013501 (2000)","journal-title":"ITA"},{"issue":"3","key":"21_CR12","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, F., Plandowski, W.: The expressibility of languages and relations by word equations. J. ACM\u00a047(3), 483\u2013505 (2000)","journal-title":"J. ACM"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Kiezun, A., Ganesh, V., Guo, P., Hooimeijer, P., Ernst, M.: HAMPI: a solver for string constraints. In: Rothermel, G., Dillon, L. (eds.) ISSTA, pp. 105\u2013116. ACM (2009)","DOI":"10.1145\/1572272.1572286"},{"key":"21_CR14","unstructured":"Majumdar, R.: Private correspondence. SWS, MPI, Kaiserslautern, Germany (2010)"},{"key":"21_CR15","first-page":"147","volume":"103","author":"G. Makanin","year":"1977","unstructured":"Makanin, G.: The problem of solvability of equations in a free semigroup. Math. Sbornik\u00a0103, 147\u2013236 (1977); English transl. in Math USSR Sbornik 32 (1977)","journal-title":"Math. Sbornik"},{"issue":"1","key":"21_CR16","first-page":"196","volume":"23","author":"S.S. Marchenkov","year":"1982","unstructured":"Marchenkov, S.S.: Unsolvability of positive \u2200\u2009\u2203-theory of free semi-group. Sibirsky Mathmatichesky Jurnal\u00a023(1), 196\u2013198 (1982)","journal-title":"Sibirsky Mathmatichesky Jurnal"},{"key":"21_CR17","unstructured":"Matiyasevich, Y.: Word equations, Fibonacci numbers, and Hilbert\u2019s tenth problem (2006) (unpublished), \n                  \n                    http:\/\/logic.pdmi.ras.ru\/?yumat\/Journal\/jcontord.htm"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-0-387-68546-5_4","volume-title":"New Computational Paradigms","author":"Y. Matiyasevich","year":"2008","unstructured":"Matiyasevich, Y.: Computation paradigms in light of Hilbert\u2019s Tenth Problem. In: Cooper, S., L\u00f6we, B., Sorbi, A. (eds.) New Computational Paradigms, pp. 59\u201385. Springer, New York (2008)"},{"key":"21_CR19","unstructured":"M\u00f6ller, O.: \u2203\u2009BV\n                [n]\n                solvability. SRI International, Menlo Park, CA, USA (October 1996) (unpublished manuscript)"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Satisfiability of word equations with constants is in PSPACE. In: FOCS, pp. 495\u2013500. IEEE Computer Society (1999)","DOI":"10.1145\/301250.301443"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: An efficient algorithm for solving word equations. In: Kleinberg, J. (ed.) STOC, pp. 467\u2013476. ACM (2006)","DOI":"10.1145\/1132516.1132584"},{"key":"21_CR22","unstructured":"Presburger, M.: \u00dcber de vollst\u00e4ndigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchen, die addition als einzige operation hervortritt. In: Comptes Rendus du Premier Congr\u00e8s des Math\u00e9maticienes des Pays Slaves, Warsaw, pp. 92\u2013101, 395 (1927)"},{"issue":"4","key":"21_CR23","doi-asserted-by":"publisher","first-page":"105","DOI":"10.2307\/2268308","volume":"11","author":"W.V. Quine","year":"1946","unstructured":"Quine, W.V.: Concatenation as a basis for arithmetic. The Journal of Symbolic Logic\u00a011(4), 105\u2013114 (1946)","journal-title":"The Journal of Symbolic Logic"},{"key":"21_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-49116-3_20","volume-title":"STACS 99","author":"J.M. Robson","year":"1999","unstructured":"Robson, J.M., Diekert, V.: On quadratic word equations. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 217\u2013226. Springer, Heidelberg (1999)"},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Saxena, P., Akhawe, D., Hanna, S., Mao, F., McCamant, S., Song, D.: A symbolic execution framework for JavaScript. In: IEEE Symposium on Security and Privacy, pp. 513\u2013528. IEEE Computer Society (2010)","DOI":"10.1109\/SP.2010.38"},{"key":"21_CR26","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-two improvements and a generalization. In: Schulz, K.U. (ed.) IWWERT 1990. LNCS, vol.\u00a0572, pp. 85\u2013150. Springer, Heidelberg (1992)"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Wassermann, G., Su, Z.: Sound and precise analysis of web applications for injection vulnerabilities. In: Ferrante, J., McKinley, K. (eds.) PLDI, pp. 32\u201341. ACM (2007)","DOI":"10.1145\/1273442.1250739"}],"container-title":["Lecture Notes in Computer Science","Hardware and Software: Verification and Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39611-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T10:24:17Z","timestamp":1557915857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39611-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642396106","9783642396113"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39611-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}