中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 会议论文
Title:
A linear-time complexity algorithm for solving the dyck-cfl reachability problem on bi-directed trees
Author: Sun, Xiaoshan (1) ; Zhang, Yang (2) ; Cheng, Liang (2)
Conference Name: 5th International Conference on Machine Vision: Computer Vision, Image Analysis and Processing, ICMV 2012
Conference Date: October 20, 2012 - October 21, 2012
Issued Date: 2013
Conference Place: Wuhan, China
Publish Place: SPIE, P.O. Box 10, Bellingham, WA 98227-0010, United States
Indexed Type: EI
ISSN: 0277786X
ISBN: 9780819495877
Department: (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
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.
English 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.
Language: 英语
Content Type: 会议论文
URI: http://ir.iscas.ac.cn/handle/311060/16654
Appears in Collections:软件所图书馆_会议论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
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.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Sun, Xiaoshan (1)]'s Articles
[Zhang, Yang (2)]'s Articles
[Cheng, Liang (2)]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Sun, Xiaoshan (1)]‘s Articles
[Zhang, Yang (2)]‘s Articles
[Cheng, Liang (2)]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2020  中国科学院软件研究所 - Feedback
Powered by CSpace