Name
Abstract | ||
|---|---|---|
Decision procedures have long been a fixture in program analysis, and reasoning about string constraints is a key element in many program analyses and testing frameworks. Recent work on string analysis has focused on providing decision procedures that model string operations. Separating string analysis from its client applications has important and familiar benefits: it enables the independent improvement of string analysis tools and it saves client effort. We present a constraint solving algorithm for equations over string variables. We focus on scalability with regard to the size of the input constraints. Our algorithm performs an explicit search for a satisfying assignment; the search space is constructed lazily based on an automata representation of the constraints. We evaluate our approach by comparing its performance with that of existing string decision procedures. Our prototype is, on average, several orders of magnitude faster than the fastest existing implementation |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1858996.1859080 | Automated Software Engineering |
Keywords | Field | DocType |
String,Regular language,Decision procedure,Scalability | String searching algorithm,Fixture,Computer science,Automaton,Theoretical computer science,Regular language,Program analysis,String metric,String operations,Scalability | Conference |
Volume | Issue | Citations |
19 | 4 | 25 |
PageRank | References | Authors |
0.98 | 26 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pieter Hooimeijer | 1 | 598 | 26.19 |
| Westley Weimer | 2 | 3510 | 162.27 |