Interconvertibility 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 an 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.
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin