QQ客服 官方微博 反馈留言

	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
中文摘要	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.
收录类别	EI
会议录出版地	SPIE, P.O. Box 10, Bellingham, WA 98227-0010, United States
语种	英语
ISSN号	0277786X
ISBN号	9780819495877
内容类型	会议论文
源URL	[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]. 见:5th International Conference on Machine Vision: Computer Vision, Image Analysis and Processing, ICMV 2012. Wuhan, China. October 20, 2012 - October 21, 2012.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。