A linear-time complexity algorithm for solving the Dyck-CFL reachability problem on bi-directed trees
Xiaoshan Sun, Yang Zhang, Liang Cheng · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2013
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 naïve algorithm runs in O(n2) 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.