结构化Petri网抑制弧最小初始标记算法

"这篇文章主要探讨了具有抑制弧的结构化Petri网的最小初始标记问题。抑制弧使得Petri网的表达能力增强，但同时也带来了分析的复杂性。文章研究了在普通Petri网及其抑制弧扩展版本中，结构活性（structural liveness）的必要和充分条件，并提出了一种新的算法来解决如何在结构活性的Petri网中分配最少数量的令牌以保证网络的活性。此算法能在多项式时间内完成，避免了全面枚举所有可能标记的缺点。" Petri网是一种用于建模并发系统和动态过程的图形理论工具，它由地方（places）、转移（transitions）和弧线（arcs）组成。普通Petri网中的弧线通常表示令牌的流动，而抑制弧（inhibitor arcs）则引入了一种负反馈机制，可以阻止某些转移的触发，增加了模型的灵活性和复杂性。 在具有抑制弧的Petri网中，结构活性是一个重要的概念，它表示网络即使在没有外部输入的情况下也能保持动态行为。然而，抑制弧的存在使得从普通Petri网继承的一些属性，如活性，可能不再成立。因此，文章着重研究了如何在这样的网络中判断其结构活性，并给出了决定这一属性的必要和充分条件。 在结构活性的Petri网中，一个关键问题是找到最小初始标记（minimum initial marking），即网络中所需的最少令牌数，使得网络能够启动并保持活动。传统的解决方案可能需要遍历所有可能的标记组合，这在大型网络中效率极低。文章提出了一种创新算法，该算法仅在关键位置放置令牌，能在多项式时间内找到最优解，显著提升了计算效率。 通过这种方法，文章提供了一种有效且实用的工具，不仅解决了具有抑制弧的Petri网的结构活性判定问题，还为最小初始标记的求解提供了高效策略。这对于理解和设计复杂的并发系统、验证其动态行为以及优化资源分配等问题具有重要意义。 这篇论文为Petri网理论和应用领域贡献了新的见解和实用技术，特别是在处理抑制弧带来的挑战时，提出的算法为实际系统建模和分析提供了强大支持。