Accession Number:

AD1004547

Title:

Interconvertibility of a Class of Set Constraints and Context-Free-Language Reachability

Descriptive Note:

Journal Article

Corporate Author:

University of Wisconsin Madison United States

Personal Author(s):

• Melski,David
• Reps,Thomas

Report Date:

1998-12-04

Pagination or Media Count:

55.0

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

Descriptors:

• COMPUTER LOGIC
• CONTEXT FREE GRAMMARS
• algorithms

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE