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 条
[131]   A VARIANT OF A RECURSIVELY UNSOLVABLE PROBLEM [J].
POST, EL .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (04) :264-268
[132]  
Py-Conbyte Team, 2021, PY CONB PYTH CONC TE
[133]  
Quimper CG, 2006, LECT NOTES COMPUT SC, V4204, P751
[134]  
Quine W.V., 1946, J SYMBOLIC LOGIC, V11, P105
[135]  
Rajasekar A., 1994, Principles and Practice of Constraint Programming. Second International Workshop, PPCP '94. Proceedings, P109
[136]   A Decision Procedure for String to Code Point Conversion [J].
Reynolds, Andrew ;
Notzli, Andres ;
Barrett, Clark ;
Tinelli, Cesare .
AUTOMATED REASONING, PT I, 2020, 12166 :218-237
[137]   High-Level Abstractions for Simplifying Extended String Constraints in SMT [J].
Reynolds, Andrew ;
Notzli, Andres ;
Barrett, Clark ;
Tinelli, Cesare .
COMPUTER AIDED VERIFICATION, CAV 2019, PT II, 2019, 11562 :23-42
[138]   Scaling Up DPLL(T) String Solvers Using Context-Dependent Simplification [J].
Reynolds, Andrew ;
Woo, Maverick ;
Barrett, Clark ;
Brumley, David ;
Liang, Tianyi ;
Tinelli, Cesare .
COMPUTER AIDED VERIFICATION (CAV 2017), PT II, 2017, 10427 :453-474
[139]  
Robson JM, 1999, LECT NOTES COMPUT SC, V1563, P217
[140]  
Rossi F, 2006, FOUND ARTIF INTELL, P1
9101112131415161718