论文标题
工作流网中的声音的复杂性
The complexity of soundness in workflow nets
论文作者
论文摘要
工作流网是Petri网的流行变体，可以对业务流程进行算法形式分析。有关工作流网络的中心决策问题涉及声音，其中指定了初始配置和最终配置。凭直觉，音质指出，从每种可触及的配置都可以达到最终配置。我们解决了三种主要声音变体的广泛开放的复杂性：经典，结构和广义的声音。前两个是expspace complete，令人惊讶的是，后者是pspace complete，因此在计算上更简单。
Workflow nets are a popular variant of Petri nets that allow for algorithmic formal analysis of business processes. The central decision problems concerning workflow nets deal with soundness, where the initial and final configurations are specified. Intuitively, soundness states that from every reachable configuration one can reach the final configuration. We settle the widely open complexity of the three main variants of soundness: classical, structural and generalised soundness. The first two are EXPSPACE-complete, and, surprisingly, the latter is PSPACE-complete, thus computationally simpler.
