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 条

[91]

IBM, 2018, SEC APPSCAN

[92] CONSTRAINT LOGIC PROGRAMMING - A SURVEY [J].

JAFFAR, J ;

MAHER, MJ .

JOURNAL OF LOGIC PROGRAMMING, 1994, 20 :503-581

[93] Recompression: A Simple and Powerful Technique for Word Equations [J].

Jez, Artur .

JOURNAL OF THE ACM, 2016, 63 (01) :1-51

[94] Grammar constraints [J].

Kadioglu, Serdar ;

Sellmann, Meinolf .

CONSTRAINTS, 2010, 15 (01) :117-144

[95]

Kausler Scott., 2014, Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering, ASE '14, P259, DOI DOI 10.1145/2642937.2643003

[96] HAMPI: A Solver for Word Equations over Strings, Regular Expressions, and Context-Free Grammars [J].