三划分问题可多项式归约为唯一可达向量Petri网可达性问题
为了对基于唯一可达向量Pe试网(URV-PN)的密码体制进行密码分析工作,有必要对唯一可达向量网系统的数学本质和各种性质进行深入的研究.定义了扩展的三划分问题,三划分问题是扩展的三划分问题的一种特殊情况;给出了一个一般的多项式时间复杂度算法构造扩展的三划分问题的Pem网模型;证明扩展的三划分问题有解当且仅当所构造的Petri网模型中某个标识可达;从而说明三划分问题可多项式归约为唯一可达向量Petri网系统的可达性问题,从而给出了求解唯一可达向量网系统可达性问题的一个复杂度下界.
Petri网 三划分问题 可达性 唯一可达向量
岳昊
山东科技大学信息学院,山东,青岛,266510;河南理工大学计算机学院,河南,焦作,454003
国内会议
扬州
中文
144-146
2008-10-25（万方平台首次上网日期，不代表论文的发表时间）