A linear-time complexity algorithm for solving the dyck-cfl reachability problem on bi-directed trees

ISCAS OpenIR

	A linear-time complexity algorithm for solving the dyck-cfl reachability problem on bi-directed trees
	Sun, Xiaoshan (1); Zhang, Yang (2); Cheng, Liang (2)
	2013
会议名称	5th International Conference on Machine Vision: Computer Vision, Image Analysis and Processing, ICMV 2012
会议日期	October 20, 2012 - October 21, 2012
会议地点	Wuhan, China
收录类别	EI
出版地	SPIE, P.O. Box 10, Bellingham, WA 98227-0010, United States
ISSN	0277786X
ISBN	9780819495877
部门归属	(1) State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing 100049, China; (2) State Key Laboratory of Information Security, Institute of Software Chinese Academy of Sciences, Beijing 100190, China
摘要	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.; 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.
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16654
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Sun, Xiaoshan ,Zhang, Yang ,Cheng, Liang . A linear-time complexity algorithm for solving the dyck-cfl reachability problem on bi-directed trees[C]. SPIE, P.O. Box 10, Bellingham, WA 98227-0010, United States,2013.