{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T23:21:12Z","timestamp":1769728872900,"version":"3.49.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319216898","type":"print"},{"value":"9783319216904","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21690-4_14","type":"book-chapter","created":{"date-parts":[[2015,7,15]],"date-time":"2015-07-15T02:08:27Z","timestamp":1436926107000},"page":"235-254","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Effective Search-Space Pruning for Solvers of String Equations, Regular Expressions and Length Constraints"],"prefix":"10.1007","author":[{"given":"Yunhui","family":"Zheng","sequence":"first","affiliation":[]},{"given":"Vijay","family":"Ganesh","sequence":"additional","affiliation":[]},{"given":"Sanu","family":"Subramanian","sequence":"additional","affiliation":[]},{"given":"Omer","family":"Tripp","sequence":"additional","affiliation":[]},{"given":"Julian","family":"Dolby","sequence":"additional","affiliation":[]},{"given":"Xiangyu","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,16]]},"reference":[{"key":"14_CR1","unstructured":"Z3str2 String constraint solver. \n                      https:\/\/sites.google.com\/site\/z3strsolver\/"},{"key":"14_CR2","unstructured":"IBM security AppScan source. \n                      http:\/\/www-03.ibm.com\/software\/products\/en\/appscan-source"},{"key":"14_CR3","unstructured":"Kausler suite. \n                      https:\/\/github.com\/BoiseState\/string-constraint-solvers"},{"key":"14_CR4","unstructured":"LibStranger. \n                      https:\/\/github.com\/vlab-cs-ucsb\/LibStranger"},{"key":"14_CR5","unstructured":"Personal communications with the stranger team (2015)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/978-3-319-08867-9_10","volume-title":"Computer Aided Verification","author":"PA Abdulla","year":"2014","unstructured":"Abdulla, P.A., Atig, M.F., Chen, Y.-F., Hol\u00edk, L., Rezine, A., R\u00fcmmer, P., Stenman, J.: String constraints for verification. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 150\u2013166. Springer, Heidelberg (2014)"},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-642-00768-2_27","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"N Bj\u00f8rner","year":"2009","unstructured":"Bj\u00f8rner, N., Tillmann, N., Voronkov, A.: Path feasibility analysis for string-manipulating programs. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol. 5505, pp. 307\u2013321. Springer, Heidelberg (2009)"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44898-5_1","volume-title":"Static Analysis","author":"AS Christensen","year":"2003","unstructured":"Christensen, A.S., M\u00f8ller, A., Schwartzbach, M.I.: Precise analysis of string expressions. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694, pp. 1\u201318. Springer, Heidelberg (2003)"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-540-78800-3_24","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"L Moura De","year":"2008","unstructured":"De Moura, L., Bj\u00f8rner, N.S.: Z3: an efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 337\u2013340. Springer, Heidelberg (2008)"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-540-73368-3_52","volume-title":"Computer Aided Verification","author":"V Ganesh","year":"2007","unstructured":"Ganesh, V., Dill, D.L.: A decision procedure for bit-vectors and arrays. In: Damm, W., Hermanns, H. (eds.) CAV 2007. LNCS, vol. 4590, pp. 519\u2013531. Springer, Heidelberg (2007)"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-642-39611-3_21","volume-title":"Hardware and Software: Verification and Testing","author":"V Ganesh","year":"2013","unstructured":"Ganesh, V., Minnes, M., Solar-Lezama, A., Rinard, M.: Word equations with length constraints: what\u2019s decidable? In: Biere, A., Nahir, A., Vos, T. (eds.) HVC. LNCS, vol. 7857, pp. 209\u2013226. Springer, Heidelberg (2013)"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Ghosh, I., Shafiei, N., Li, G., Chiang, W.-F.: JST: an automatic test generation tool for industrial java applications with strings. In: Proceedings of the 2013 International Conference on Software Engineering, ICSE 2013, pp. 992\u20131001 (2013)","DOI":"10.1109\/ICSE.2013.6606649"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Hooimeijer, P., Weimer, W.: Solving string constraints lazily. In: Proceedings of the IEEE\/ACM International Conference on Automated Software Engineering, ASE 2010, pp. 377\u2013386 (2010)","DOI":"10.1145\/1858996.1859080"},{"key":"14_CR14","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2007","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Pearson\/Addison Wesley, Upper Saddle River (2007)"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/978-3-642-38771-5_2","volume-title":"Developments in Language Theory","author":"A Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Recompression: word equations and beyond. In: B\u00e9al, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol. 7907, pp. 12\u201326. Springer, Heidelberg (2013)"},{"issue":"3","key":"14_CR16","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 47(3), 483\u2013505 (2000)","journal-title":"J. ACM"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Kausler, S.: Evaluation of string constraint solvers using dynamic symbolic execution. Master\u2019s thesis, Boise State University (2014)","DOI":"10.1145\/2642937.2643003"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Kausler, S., Sherman, E.: Evaluation of string constraint solvers in the context of symbolic execution. In: Proceedings of the 29th ACM\/IEEE International Conference on Automated Software Engineering, ASE 2014, pp. 259\u2013270. ACM, New York, NY, USA (2014)","DOI":"10.1145\/2642937.2643003"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Kiezun, A., Ganesh, V., Guo, P.J., Hooimeijer, P., Ernst, M.D.: Hampi: a solver for string constraints. In: Proceedings of the Eighteenth International Symposium on Software Testing and Analysis, ISSTA 2009, pp. 105\u2013116 (2009)","DOI":"10.1145\/1572272.1572286"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Li, G., Andreasen, E., Ghosh, I.: SymJS: automatic symbolic testing of javascript web applications. In: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, pp. 449\u2013459 (2014)","DOI":"10.1145\/2635868.2635913"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-319-03077-7_2","volume-title":"Hardware and Software: Verification and Testing","author":"G Li","year":"2013","unstructured":"Li, G., Ghosh, I.: PASS: string solving with parameterized array and interval automaton. In: Bertacco, V., Legay, A. (eds.) HVC 2013. LNCS, vol. 8244, pp. 15\u201331. Springer, Heidelberg (2013)"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/978-3-319-08867-9_43","volume-title":"Computer Aided Verification","author":"T Liang","year":"2014","unstructured":"Liang, T., Reynolds, A., Tinelli, C., Barrett, C., Deters, M.: A DPLL(T) theory solver for a theory of strings and regular expressions. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 646\u2013662. Springer, Heidelberg (2014)"},{"key":"14_CR23","first-page":"147","volume":"103","author":"GS Makanin","year":"1977","unstructured":"Makanin, G.S.: The problem of solvability of equations in a free semigroup. Math. Sbornik 103, 147\u2013236 (1977). English transl. in Math USSR Sbornik 32 (1977)","journal-title":"Math. Sbornik"},{"key":"14_CR24","unstructured":"Matiyasevich, Y.: Word equations, fibonacci numbers, and hilbert\u2019s tenth problem. In: Workshop on Fibonacci Words (2007)"},{"issue":"3","key":"14_CR25","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 51(3), 483\u2013496 (2004)","journal-title":"J. ACM"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: An efficient algorithm for solving word equations. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 467\u2013476 (2006)","DOI":"10.1145\/1132516.1132584"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Redelinghuys, G., Visser, W., Geldenhuys, J.: Symbolic execution of programs with strings. In: Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference, SAICSIT 2012, pp. 139\u2013148 (2012)","DOI":"10.1145\/2389836.2389853"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Saxena, P., Akhawe, D., Hanna, S., Mao, F., McCamant, S., Song, D.: A symbolic execution framework for javascript. In: Proceedings of the 2010 IEEE Symposium on Security and Privacy, SP 2010, pp. 513\u2013528 (2010)","DOI":"10.1109\/SP.2010.38"},{"key":"14_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 Schulz","year":"1992","unstructured":"Schulz, K.: Makanin\u2019s algorithm for word equations-two improvements and a generalization. In: Schulz, K. (ed.) Word Equations and Related Topics. LNCS, vol. 572, pp. 85\u2013150. Springer, Heidelberg (1992)"},{"issue":"4","key":"14_CR30","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/2522920.2522926","volume":"22","author":"T Tateishi","year":"2013","unstructured":"Tateishi, T., Pistoia, M., Tripp, O.: Path- and index-sensitive string analysis based on monadic second-order logic. ACM Trans. Softw. Eng. Methodol. 22(4), 33:1\u201333:33 (2013)","journal-title":"ACM Trans. Softw. Eng. Methodol."},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Trinh, M.-T., Chu, D.-H., Jaffar, J.: S3: A symbolic string solver for vulnerability detection in web applications. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS 2014, pp. 1232\u20131243 (2014)","DOI":"10.1145\/2660267.2660372"},{"key":"14_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-642-12002-2_13","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"F Yu","year":"2010","unstructured":"Yu, F., Alkhalaf, M., Bultan, T.: Stranger: an automata-based string analysis tool for PHP. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol. 6015, pp. 154\u2013157. Springer, Heidelberg (2010)"},{"key":"14_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/978-3-642-00768-2_28","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"F Yu","year":"2009","unstructured":"Yu, F., Bultan, T., Ibarra, O.H.: Symbolic string verification: combining string analysis and size analysis. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol. 5505, pp. 322\u2013336. Springer, Heidelberg (2009)"},{"key":"14_CR34","unstructured":"Zheng, Y., Ganesh, V., Subramanian, S., Tripp, O., Dolby, J., Zhang, X.: Effective search-space pruning for solvers of string equations, regular expressions and length constraints. Technical report (2015). \n                      https:\/\/sites.google.com\/site\/z3strsolver\/publications"},{"key":"14_CR35","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Zhang, X., Ganesh, V.: Z3-str: a z3-based string solver for web application analysis. In: Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC\/FSE 2013, pp. 114\u2013124 (2013)","DOI":"10.1145\/2491411.2491456"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21690-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,22]],"date-time":"2019-07-22T20:06:06Z","timestamp":1563825966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-21690-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319216898","9783319216904"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21690-4_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}