Interconvertibility of a Class of Set Constraints and
Context-Free-Language Reachability
David Melski and Thomas Reps
We show the interconvertibility of context-free-language reachability problems
and a class of set-constraint problems: given a context-free-language
reachability problem, we show how to construct a set-constraint problem whose
answer gives a solution to the reachability problem; given a set-constraint
problem, we show how to construct a context-free-language reachability problem
whose answer gives a solution to the set-constraint problem. The
interconvertibility of these two formalisms offers a conceptual advantage akin
to the advantage gained from the interconvertibility of finite-state automata
and regular expressions in formal language theory, namely, a problem can be
formulated in whichever formalism is most natural. It also offers some insight
into the ``O(n**3) bottleneck'' for different types of program-analysis
problems, and allows results previously obtained for context-free-language
reachability problems to be applied to set-constraint problems and vice versa.
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin