On Deciding Readiness and Failure Equivalences for Processes
On Deciding Readiness and Failure Equivalences for Processes
复制标题
关于确定流程的准备就绪和失败等价
DOI：
10.1006/inco.1995.1039
复制
发表时间：
1995
影响因子：
1
通讯作者：
Lu Tian
中科院分区：
文献类型：
--
作者：
D. Huynh;Lu Tian
在本文中，我们研究的复杂性，决定准备和故障等价的有限状态过程和递归定义的过程指定的赋范上下文无关文法（CFGs）在格雷巴赫范式（GNF）。结果如下：（1）赋范GNF CFG指定的过程的准备就绪性和故障等效性都是不可判定的。对于这类过程，关于故障或准备等价的正则性问题也是不可判定的。此外，所有这些不可判定性的结果，甚至保持局部一元过程。在一元的情况下，这些问题变得可判定。事实上，他们是？我们还证明了在互模拟等价下，由赋范GNF CFGs指定的过程的正则性是NL-完全的。(2)有限状态过程的准备和故障等价是PSPACE完备的。这甚至适用于局部一元有限状态过程。对于一元有限状态过程，这两个等价是co-NP-完全的。此外，对于非循环有限状态过程，准备和故障等价是co-NP-完全的，它们在一元情况下是NL-完全的。(3)对于有限树过程，我们证明了有限的跟踪，准备，和失败的等价都是L-完全的。此外，结果仍然为真的一元的情况下。我们的研究结果提供了一个完整的表征的计算复杂性，决定准备和故障等价的几个重要类别的过程。
In this paper, we study the complexity of deciding readiness and failure equivalences for finite state processes and recursively defined processes specified by normed context-free grammars (CFGs) in Greibach normal form (GNF). The results are as follows: (1) Readiness and failure equivalences for processes specified by normed GNF CFGs are both undecidable. For this class of processes, the regularity problem with respect to failure or readiness equivalence is also undecidable. Moreover, all these undecidability results hold even for locally unary processes. In the unary case, these problems become decidable. In fact, they are ?p2-complete, We also show that with respect to bisimulation equivalence, the regularity for processes specified by normed GNF CFGs is NL-complete. (2) Readiness and failure equivalences for finite state processes are PSPACE-complete. This holds even for locally unary finite state processes. These two equivalences are co-NP-complete for unary finite state processes. Further, for acyclic finite state processes, readiness and failure equivalences are co-NP-complete and they are NL-complete in the unary case. (3) For finite tree processes, we show that finite trace, readiness, and failure equivalences are all L-complete. Further, the results remain true for the unary case. Our results provide a complete characterization of the computational complexity of deciding readiness and failure equivalences for several important classes of processes.