论文标题
有效限制立即观察培养皿网
Efficient Restrictions of Immediate Observation Petri Nets
论文作者
论文摘要
在上一篇论文中，我们引入了立即观察Petri网络，这是一个具有分布式方案（人口方案）和理论化学（化学反应网络）的培养皿网的子类。 IO网享有许多有用的属性，但是与保守的培养皿网的一般情况一样，它们具有PSPACE完整的可及性问题。在本文中，我们探讨了IO网的可及性问题的两个限制，这些限制大大降低了问题的复杂性。对于在分布式协议中应用的第一个限制，复杂性是NP的完整性，并且对于在化学设置中应用的第二个限制是多项式的。
In a previous paper we introduced immediate observation Petri nets, a subclass of Petri nets with application domains in distributed protocols (population protocols) and theoretical chemistry (chemical reaction networks). IO nets enjoy many useful properties, but like the general case of conservative Petri nets they have a PSPACE-complete reachability problem. In this paper we explore two restrictions of the reachability problem for IO nets which lower the complexity of the problem drastically. The complexity is NP-complete for the first restriction with applications in distributed protocols, and it is polynomial for the second restriction with applications in chemical settings.
