petri网的步问题研究

在基于petri网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是np完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的np等价性证明.最后分析两类特殊子问题是p问题.