language: en

Interconvertibility of Set Constraints and Context-Free Language Reachability

David Melski Thomas Reps
November 18, 1996

Abstract 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 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.

David Melski Thomas Reps
Computer Sciences Department Computer Sciences Department University of Wisconsin University of Wisconsin
1210 W. Dayton St. 1210 W. Dayton St. Madison, WI 53706 Madison, WI 53706

[608/262-0016 608/262-2091]

melski@cs.wisc.edu

[608/262-9777 (fax)]

reps@cs.wisc.edu