DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Interconvertibility of a Class of Set Constraints and Context-Free-Language Reachability
University of Wisconsin Madison United States
Pagination or Media Count:
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 On3 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.
APPROVED FOR PUBLIC RELEASE