空标识可再生网的运算和性质分析

Lautenbach等人曾给出了一般网空标识可再生 (reproducibility of the empty marking)的充要条件,证明了一个网是空标识可再生的,必须存在含有源(fact)和汇(goal)变迁的非负T-不变,且由该T-不变所组成的变迁外延子网既不含有死锁(siphon),也不含有陷阱(trap).扩展了这个结论,证明了经合成、插入、删除、替换等运算后的网仍保持空标识可再生性.还进一步证明了空标识可再生网的逆网也是空标识可再生的;无环空标识可再生Horn网的T-不变一定可实现;一个含有源和汇变迁的无环P/T网是空标识可再生的,当且仅当其被T-不变所覆盖.这些结论可为复杂的逻辑推理及工作流逻辑网的畅通性检测提供更为有效的方法,最后给出了相应的算法.