On the complexity of bidirected interleaved Dyck-reachability
On the complexity of bidirected interleaved Dyck-reachability
复制标题
双向交错Dyck可达性的复杂性
DOI：
10.1145/3434340
复制
发表时间：
2021
影响因子：
--
通讯作者：
Reps, Thomas
中科院分区：
文献类型：
--
作者：
Li, Yuanbo;Zhang, Qirun;Reps, Thomas
许多程序分析需要对匹配操作对进行推理，例如调用/返回、锁定/解锁或设置字段/获取字段。DYCK语言家族{DK}，其中Dkhask种类的括号对可用于将匹配动作建模为对括号。因此，许多程序分析问题可以表示为边标记有向图上的DYCK-可达性问题。交错DYCK-可达性，表示为Dk⊙DK-可达性，是DYCK-可达性的自然扩展，它允许人们描述涉及多种匹配-动作对的程序分析问题。不幸的是，一般的互Dyck-可达性问题是不可判定的.本文研究了有向图的互Dyck-可达性的变体，其中对每个边⟨p，q⟩用开括号“(a”，有一个边⟨q，p⟩由相应的闭括号“)a”标记，反之亦然.双向图上的语言可达性已被证明是有用的：(1)作为形式化许多程序分析问题的方法，如指针分析；(2)作为一种放松方法，使用快速算法来过度逼近有向图上的语言可达性。然而，不同于它的有向对应者，双向相互Dyck-可达性的复杂性仍然是开放的。我们建立了双向相互Dyck-可达性的第一个可判定变体(即，d1⊙d1-可达性)。在d1⊙d1可达性中，两种DYCK语言中的每一种都被限制为只有一种括号对。特别地，我们证明了双向D_1⊙D_1问题在ptime内。我们还证明了当扩展每种DYCK语言到包含不同类型的括号(即DK⊙DK-可达性与k≥2)时，问题是NP难的(因此困难得多)。我们实现了bidirectedD1⊙D1-reachability.Dk⊙Dk-reachability的多项式时间算法，在Dk⊙DK-可达性可以首先放宽为双向Dk-⊙DK-可达性的意义下，提供了一种新的过逼近方法，从而精确地解决了所得到的双向Dk-⊙D1-可达性问题。我们将这种基于D1⊙D1可达性的方法与另一种已知的过逼近Dk⊙DK可达性算法进行了比较。令人惊讶的是，我们发现基于双向d1⊙d1可达性的过近似方法计算出更精确的解，尽管d1⊙d1形式的表达能力天生不如Dk⊙dk形式。
Many program analyses need to reason about pairs of matching actions, such as call/return, lock/unlock, or set-field/get-field. The family of Dyck languages {Dk}, whereDkhaskkinds of parenthesis pairs, can be used to model matching actions as balanced parentheses. Consequently, many program-analysis problems can be formulated as Dyck-reachability problems on edge-labeled digraphs.Interleaved Dyck-reachability(InterDyck-reachability), denoted byDk⊙Dk-reachability, is a natural extension of Dyck-reachability that allows one to formulate program-analysis problems that involvemultiplekinds of matching-action pairs. Unfortunately, the general InterDyck-reachability problem is undecidable.In this paper, we study variants of InterDyck-reachability onbidirected graphs, where for each edge ⟨p,q⟩ labeled by an open parenthesis ”(a”, there is an edge ⟨q,p⟩ labeled by the corresponding close parenthesis ”)a”, andvice versa. Language-reachability on a bidirected graph has proven to be useful both (1) in its own right, as a way to formalize many program-analysis problems, such as pointer analysis, and (2) as arelaxationmethod that uses a fast algorithm to over-approximate language-reachability on a directed graph. However, unlike its directed counterpart, the complexity of bidirected InterDyck-reachability still remains open.We establish the first decidable variant (i.e.,D1⊙D1-reachability) of bidirected InterDyck-reachability. InD1⊙D1-reachability, each of the two Dyck languages is restricted to have only a single kind of parenthesis pair. In particular, we show that the bidirectedD1⊙D1problem is in PTIME. We also show that when one extends each Dyck language to involvekdifferent kinds of parentheses (i.e.,Dk⊙Dk-reachability withk≥ 2), the problem is NP-hard (and therefore much harder).We have implemented the polynomial-time algorithm for bidirectedD1⊙D1-reachability.Dk⊙Dk-reachability provides a new over-approximation method for bidirectedDk⊙Dk-reachability in the sense thatDk⊙Dk-reachability can first be relaxed to bidirectedD1⊙D1-reachability, and then the resulting bidirectedD1⊙D1-reachability problem is solved precisely. We compare thisD1⊙D1-reachability-based approach against another known over-approximatingDk⊙Dk-reachability algorithm. Surprisingly, we found that the over-approximation approach based on bidirectedD1⊙D1-reachability computesmore precisesolutions, even though theD1⊙D1formalism is inherently less expressive than theDk⊙Dkformalism.
登录
查看更多内容
DOI：
10.1145/3385412.3386021
发表时间：
2020-06
期刊：
Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Yuanbo Li;Qirun Zhang;T. Reps
通讯作者：
Yuanbo Li;Qirun Zhang;T. Reps
锁链的有界性与无界性：表征成对 CFL 的可判定性 - 通过锁进行通信的线程的可达性
DOI：
10.1109/lics.2009.45
发表时间：
2009
期刊：
2009 24th Annual IEEE Symposium on Logic In Computer Science
影响因子：
--
作者：
Vineet Kahlon
通讯作者：
Vineet Kahlon
程序测试路径生成中的两个问题的探讨
影响因子：
7.4
作者：
H. Gabow;Shachindra N. Maheswari;L. Osterweil
通讯作者：
L. Osterweil
DOI：
10.1089/cmb.2013.0004
发表时间：
2011
期刊：
Journal of computational biology : a journal of computational molecular cell biology
影响因子：
--
作者：
Jakub Kovác
通讯作者：
Jakub Kovác