Share Email Print
cover

Proceedings Paper

A linear-time complexity algorithm for solving the Dyck-CFL reachability problem on bi-directed trees
Author(s): Xiaoshan Sun; Yang Zhang; Liang Cheng
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 13 March 2013
PDF: 6 pages
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
Show Author Affiliations
Xiaoshan Sun, Institute of Software (China)
Yang Zhang, Graduate School of the Chinese Academy of Sciences (China)
Liang Cheng, Graduate School of the Chinese Academy of Sciences (China)


Published in SPIE Proceedings Vol. 8783:
Fifth International Conference on Machine Vision (ICMV 2012): Computer Vision, Image Analysis and Processing
Yulin Wang; Liansheng Tan; Jianhong Zhou, Editor(s)

© SPIE. Terms of Use
Back to Top