Partially-commutative context-free processes: Expressibility and tractability
Partially-commutative context-free processes: Expressibility and tractability
复制标题
部分交换的上下文无关过程：可表达性和易处理性
DOI：
10.1016/j.ic.2010.12.003
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
S. Lasota
中科院分区：
文献类型：
--
作者：
Wojciech Czerwinski;Sibylle B. Fröschle;S. Lasota
对于顺序和交换范数上下文无关过程（分别称为 BPA 和 BPP），双模拟等价均可在多项式时间内判定。尽管这两个类别之间存在明显的相似性，但每种情况都使用了不同的算法技术。我们提供了一种多项式时间算法，该算法适用于规范 BPA 和 BPP 的超类。它是在部分交换的上下文无关进程的设置中导出的，这是本文中引入的一个新进程类。它包含 BPA 和 BPP，并且似乎具有独立的利益。与规范的 PA 类相比，新类的可表达性问题也在本文中得到解决。
Bisimulation equivalence is decidable in polynomial time for both sequential and commutative normed context-free processes, known as BPA and BPP, respectively. Despite apparent similarity between the two classes, different algorithmic techniques were used in each case. We provide one polynomial-time algorithm that works in a superclass of both normed BPA and BPP. It is derived in the setting of partially-commutative context-free processes, a new process class introduced in the paper. It subsumes both BPA and BPP and seems to be of independent interest. Expressibility issue of the new class, in comparison with the normed PA class, is also tackled in the paper.