• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on machine vision >A Linear-Time Complexity Algorithm for Solving the Dyck-CFL Reachability Problem on Bi-directed Trees
【24h】

A Linear-Time Complexity Algorithm for Solving the Dyck-CFL Reachability Problem on Bi-directed Trees

机译：一种用于解决双向树木Dyck-CFL可达性问题的线性时间复杂度算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 naieve algorithm runs in O(n~2) 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.
机译：今天，许多错误检测工具使用静态程序分析技术来发现程序中的漏洞，并且许多静态程序分析可以转换为CFL（无背景）可达性问题，其中大多数是Dyck-CFL到达性问题，特定的类基于DYCK语言的CFL可达性问题。为了加速使用Dyck-CFL到达性问题制定的静态分析，当考虑的图表是具有特定约束的图形时，我们提出了一种o（n）时间的o（n）时间的算法，对于具有特定约束的分析。算法在O（n〜2）时间内运行。这是由双向树合并和一种有效的方法来完成，以确定从源到目的地的定向路径的存在。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号