Unbounded Model-Checking with Interpolation for Regular Language Constraints
Lists
Only you see this
Abstract
We present a decision procedure for the problem of, given a set of regular expressions R 1, …, R n , determining whether R = R 1 ∩ ⋯ ∩ R n is empty. Our solver, revenant, finitely unrolls automata for R 1, …, R n , encoding each as a set of propositional constraints. If a SAT solver determines satisfiability then R is non-empty. Otherwise our solver uses unbounded model checking techniques to extract an interpolant from the bounded proof. This interpolant serves as an overapproximation of R. If the solver reaches a fixed-point with the constraints remaining unsatisfiable, it has proven R to be empty. Otherwise, it increases the unrolling depth and repeats. We compare revenant with other state-of-the-art string solvers. Evaluation suggests that it behaves better for constraints that express the intersection of sets of regular languages, a case of interest in the context of verification.
BibTeX
@inproceedings{gange2013unbounded,
author = {Graeme Gange and Jorge A. Navas and Peter J. Stuckey and Harald Søndergaard and Peter Schachte},
title = {{Unbounded Model-Checking with Interpolation for Regular Language Constraints}},
booktitle = {TACAS},
year = {2013},
doi = {10.1007/978-3-642-36742-7\_20},
}Loading related content...