论文标题
p时间事件图的一致性弱
Weak consistency of P-time event graphs
论文作者
论文摘要
P时事件图（P-TEGS）是事件图，在该事件图中，令牌在某些地方的停留时间由指定的时间窗口界定。在本文中，我们定义了PTEG的新属性，称为弱一致性。在弱一致的P-TEG中，在第一次违反时间限制之前，过渡可以发射的次数可以根据需要将其大大。我们展示了该属性的实际含义，并基于图理论的先前结果，我们制定了一种强烈多项式时间复杂性的算法来验证它。从该算法中，可以在伪多项式时间内确定P-TEG首次违反第一次约束之前的发射数量。
P-time event graphs (P-TEGs) are event graphs where the residence time of tokens in places is bounded by specified time windows. In this paper, we define a new property of PTEGs, called weak consistency. In weakly consistent P-TEGs, the amount of times a transition can fire before the first violation of a time constraint can be made as large as desired. We show the practical implications of this property and, based on previous results in graph theory, we formulate an algorithm of strongly polynomial time complexity that verifies it. From this algorithm, it is possible to determine, in pseudo-polynomial time, the maximum number of firings before the first constraint violation in a P-TEG.
