Paper Info
Title
An evaluation of automata algorithms for string analysis
Abstract
There has been significant recent interest in automated reasoning techniques, in particular constraint solvers, for string variables. These techniques support a wide variety of clients, ranging from static analysis to automated testing. The majority of string constraint solvers rely on finite automata to support regular expression constraints. For these approaches, performance depends critically on fast automata operations such as intersection, complementation, and determinization. Existing work in this area has not yet provided conclusive results as to which core algorithms and data structures work best in practice. In this paper, we study a comprehensive set of algorithms and data structures for performing fast automata operations. Our goal is to provide an apples-to-apples comparison between techniques that are used in current tools. To achieve this, we re-implemented a number of existing techniques. We use an established set of regular expressions benchmarks as an indicative workload. We also include several techniques that, to the best of our knowledge, have not yet been used for string constraint solving. Our results show that there is a substantial performance difference across techniques, which has implications for future tool design.
Year
DOI
Venue
2011
10.1007/978-3-642-18275-4_18
VMCAI
Keywords
Field
DocType
automata algorithm,regular expression constraint,automated reasoning technique,fast automata operation,particular constraint solvers,automated testing,automata operation,string constraint,string analysis,string variable,data structure,string constraint solvers,software development,regular expression,static analysis,finite automata,automated reasoning
Data structure,Automated reasoning,Regular expression,Workload,Computer science,Automaton,Static analysis,Algorithm,Theoretical computer science,Constraint satisfaction problem,Finite-state machine
Conference
Volume
ISSN
Citations 
6538
0302-9743
27
PageRank 
References 
Authors
1.03
27
2
Name
Order
Citations
PageRank
Pieter Hooimeijer159826.19
Margus Veanes299961.26