Program plan matching: experiments with a constraint-based approach

The plan matching problem is to determine whether a program plan is present in a program. This problem has been shown to be NP-hard, which makes it an open question whether plan matching algorithms can be developed that scale sufficiently well to be useful in practice. This paper discusses experimen ts in the scalability of a series of constraint-based program plan matching algorithms we have developed. These empirical studies have led to signific ant improvements in the scalability of our plan matching algorithm, and the y suggest that this algorithm can be successfully applied to large, real-wo rld programs. (C) 2000 Elsevier Science B.V. All rights reserved.