Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems
Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems
复制标题
通过地面树重写系统细化进程重写系统层次结构
DOI：
10.1145/2629679
复制
发表时间：
2014
影响因子：
0.5
通讯作者：
Göller S
中科院分区：
文献类型：
--
作者：
Göller S
在他的开创性论文中，Mayr介绍了著名的进程重写系统（PRS）层次结构，其中包含许多研究得很好的无限状态系统，包括下推系统（PDS），Petri网和PA进程。重写社区中的一个单独的开发引入了地面树重写系统（GTRS）的概念，这是一个严格扩展PDS的模型，同时仍然享有理想的可判定属性。在GTRS和PRS层次结构中的模型（如PA和PAD过程）上，已被证明可判定（和不可判定）的验证问题之间有惊人的相似之处。减贫战略和全球贸易和RS在表达能力方面的联系程度尚不清楚。在这篇文章中，我们指出了GTRS和模型之间的确切联系，在PRS层次结构的表达能力方面的强，弱，分支互模拟。除其他外，这种连接使我们能够提供新的见解的可判定性结果的PRS的子类，如更简单的证明已知的可判定性结果的验证问题的PAD。
In his seminal paper, Mayr introduced the well-known process rewrite systems (PRS) hierarchy, which contains many well-studied classes of infinite-state systems including pushdown systems (PDS), Petri nets, and PA-processes. A separate development in the term rewriting community introduced the notion of ground tree rewrite systems (GTRS), which is a model that strictly extends PDS while still enjoying desirable decidable properties. There have been striking similarities between the verification problems that have been shown decidable (and undecidable) over GTRS and over models in the PRS hierarchy such as PA and PAD processes. It is open to what extent PRS and GTRS are connected in terms of their expressive power. In this article, we pinpoint the exact connection between GTRS and models in the PRS hierarchy in terms of their expressive power with respect to strong, weak, and branching bisimulation. Among others, this connection allows us to give new insights into the decidability results for subclasses of PRS, such as simpler proofs of known decidability results of verifications problems on PAD.
登录
查看更多内容
流程重写系统的可达性分析
DOI：
10.1007/978-3-540-24597-1_7
发表时间：
2003
期刊：
Proceedings of Tenth Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
A. Bouajjani;Tayssir Touili
通讯作者：
Tayssir Touili
DOI：
10.1016/0304-3975(85)90087-8
发表时间：
1985
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
D. E. Muller;P. Schupp
通讯作者：
D. E. Muller;P. Schupp
DOI：
10.1016/s0304-3975(00)00101-8
发表时间：
2001-04
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Richard Mayr
通讯作者：
Richard Mayr
DOI：
10.1109/lics.2011.36
发表时间：
2011-06
期刊：
2011 IEEE 26th Annual Symposium on Logic in Computer Science
影响因子：
--
作者：
Stefan Göller;A. Lin
通讯作者：
Stefan Göller;A. Lin
DOI：
10.1016/s0304-3975(00)00306-6
发表时间：
1998-09
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
D. Lugiez;P. Schnoebelen
通讯作者：
D. Lugiez;P. Schnoebelen