13 March 2013 A linear-time complexity algorithm for solving the Dyck-CFL reachability problem on bi-directed trees
Author Affiliations +
Abstract
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.
© (2013) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Xiaoshan Sun, Xiaoshan Sun, Yang Zhang, Yang Zhang, Liang Cheng, Liang Cheng, } "A linear-time complexity algorithm for solving the Dyck-CFL reachability problem on bi-directed trees", Proc. SPIE 8783, Fifth International Conference on Machine Vision (ICMV 2012): Computer Vision, Image Analysis and Processing, 87831O (13 March 2013); doi: 10.1117/12.2021187; https://doi.org/10.1117/12.2021187
PROCEEDINGS
6 PAGES


SHARE
RELATED CONTENT

Test case set generation method on MC DC based on...
Proceedings of SPIE (March 12 2013)
A fast practical feature point matching algorithm
Proceedings of SPIE (September 24 2003)
Image dense matching based on Delauney triangulation
Proceedings of SPIE (September 23 1998)
Vision-Aided Flexible Component Handling
Proceedings of SPIE (February 28 1990)

Back to Top