Institutional Repository
| 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 | |
| Conference Name | 5th International Conference on Machine Vision: Computer Vision, Image Analysis and Processing, ICMV 2012 |
| Conference Date | October 20, 2012 - October 21, 2012 |
| Conference Place | Wuhan, China |
| Indexed Type | EI |
| Publish Place | SPIE, P.O. Box 10, Bellingham, WA 98227-0010, United States |
| 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 |
| 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.; 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 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment