An Efficient Solution to Bounded Context-Free Grammar Intersection Problem

Abstract

Many program analysis and model checking problems can efficiently be solved by transforming these problems into Context-Free Grammar Intersection (CFGI) problem which is the problem of finding a sentence that can be generated by two arbitrary context-free grammars. The CFGI problem is undecidable in general. A common practical strategy for finding the solution of CFGI problem is to fix the length of sentences that can be generated by both grammars and then to find a sentence common to both grammars of the length. By fixing the length, the CFGI problem becomes NP-Complete. Recently many practically efficient solutions for bounded CFGI problem have been proposed and implemented. All these methods apply a general strategy for finding the solution of CFGI problem. Because of the generalized nature of the solutions, their implementations are not equally effective for every instance. This can be shown by testing these implementations for higher length instances. For many higher length instances these software show poor performance. In this thesis, we propose an efficient algorithm for finding solution of CFGI problem using specialized techniques that are based on the structure of given grammars. The structure of given grammars is overlooked by previous solutions due to their general strategy of finding a single solution for all pairs of grammars. In addition, we make use of memoization and agressive decision making in our solution. Our experimental results show that proposed features work better than general strategies proposed in previous solutions for many test cases. For some test cases we still need more analysis to get better performance than general strategies.