一类同步合成网合法发射序列判定的一个多项式时间算法  

作　　者：蒋昌俊[1] 

机构地区：[1]同济大学计算机科学与工程系

出　　处：《中国科学（E辑）》2002年第1期116-124,共9页Science in China(Series E)

基　　金：国家自然科学基金(批准号:6973029;69933020);国家杰出青年科学基金(60125205);国家重点基础研究计划(C1998030604);全国优秀博士论文作者专项基金(199934);上海市曙光基金;上海市重点基础研究计划;教育部优秀青年教师教学科研奖励计划和山东省优秀

摘　　要：研究了同步合成网的语言性质,针对一类同步合成网,提出合法发射序列的一个多项式判定算法.从而将这类问题的多项式可解性从坚持网、无冲突网和状态机网的仅有Petri网子类,推广到更为广泛的这些子类的同步合成Petri网.一般Petri网的这类问题的判定是NP完全问题.因此,寻求这类问题的多项式可解性的任何更广网类的判定算法一直是重要的研究课题.

关 键 词：同步合成网 合法发射序列 多项式时间算法 PETRI网 网论 判定算法 NP完全问题 多项式复杂性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]