A Survey on String Constraint Solving

被引：23
作者：
Amadini, Roberto [1 ]
机构：
[1] Univ Bologna, Mura Anteo Zamboni 7, I-40126 Bologna, Italy
来源：
ACM COMPUTING SURVEYS | 2023年 / 55卷 / 01期
关键词：
String constraint solving; constraint programming; satisfiability modulo theories; automata theory; software analysis; REGULAR EXPRESSIONS; ABSTRACT DOMAINS; WORD EQUATIONS; LOGIC; LANGUAGE; GRAMMAR; SATISFIABILITY; MINIZINC; SOLVER;
D O I：
10.1145/3484198
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the past few years given the massive use of strings in different application domains like formal analysis, automated testing, database query processing, and cybersecurity. This article reports a comprehensive survey on string constraint solving by exploring the large number of approaches that have been proposed over the past few decades to solve string constraints.
引用
收藏
页数：38
相关论文
共 178 条
[121]  
Minamide Yasuhiko, PHP STRING AN
[122]   Model Counting for Recursively-Defined Strings [J].
Minh-Thai Trinh ;
Chu, Duc-Hiep ;
Jaffar, Joxan .
COMPUTER AIDED VERIFICATION (CAV 2017), PT II, 2017, 10427 :399-418
[123]   Progressive Reasoning over Recursively-Defined Strings [J].
Minh-Thai Trinh ;
Chu, Duc-Hiep ;
Jaffar, Joxan .
COMPUTER AIDED VERIFICATION, (CAV 2016), PT I, 2016, 9779 :218-240
[124]   S3: A Symbolic String Solver for Vulnerability Detection in Web Applications [J].
Minh-Thai Trinh ;
Duc-Hiep Chu ;
Jaffar, Joxan .
CCS'14: PROCEEDINGS OF THE 21ST ACM CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY, 2014, :1232-1243
[125]  
Mohri Mehryar., 2001, Robustness in Language and Speech Technology, P153, DOI DOI 10.1007/978-94-015-9719-7_6
[126]  
Nethercote N, 2007, LECT NOTES COMPUT SC, V4741, P529
[127]   Propagation via lazy clause generation [J].
Ohrimenko, Olga ;
Stuckey, Peter J. ;
Codish, Michael .
CONSTRAINTS, 2009, 14 (03) :357-391
[128]  
Pesant G, 2004, LECT NOTES COMPUT SC, V3258, P482
[129]   Satisfiability of word equations with constants is in PSPACE [J].
Plandowski, W .
JOURNAL OF THE ACM, 2004, 51 (03) :483-496
[130]  
Plandowski W., 2006, STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, P467, DOI 10.1145/1132516.1132584
891011121314151617