A Linear-Time Complexity Algorithm for Solving the Dyck-CFL Reachability Problem on Bi-directed Trees

摘要

Today many bug detecting tools use static program analysis techniques to discover the vulnerabilities in programs, and many static program analyses can be converted to CFL (Context-Free-Language) reachability problems, most of which are Dyck-CFL reachability problems, a particular class of CFL reachability problems based on Dyck languages. In order to speed up the static analyses formulated using the Dyck-CFL reachability problems, we propose an efficient algorithm of O(n) time for the Dyck-CFL reachability problem when the graph considered is a bidirected tree with specific constraints, while a naive algorithm runs in O(n:) time. This is done by the bidirected-tree merging and an efficient method to determine the existence of the directed-path from the source to the destination.