| 一类同步合成网合法发射序列判定的一个多项式时间算法 |
| |
| 作者姓名： | 蒋昌俊 |
| |
| 作者单位： | 同济大学计算机科学与工程系,上海,200092,山东科技大学计算机科学系,泰安,271019 |
| |
| 基金项目： | 国家自然科学基金（批准号:6973029,69933020），国家杰出青年科学基金（60125205），国家重点基础研究计划（C1998030604），全国优秀博士论文作者专项基金（199934），上海市曙光基金，上海市重点基础研究计划，教育部优秀青年教师教学科研奖励计划和山东省优秀 |
| |
| 摘 要： | 研究了同步合成网的语言性质，针对一类同步合成网，提出合法发射序列的一个多项式判定算法. 从而将这类问题的多项式可解性从坚持网、无冲突网和状态机网的仅有Petri网子类，推广到更为广泛的这些子类的同步合成Petri网. 一般Petri网的这类问题的判定是NP完全问题. 因此，寻求这类问题的多项式可解性的任何更广网类的判定算法一直是重要的研究课题.
|
| 关 键 词： | 同步合成 合法发射序列 判定算法 NP完全问题 多项式复杂性 Petri网 |
| 收稿时间： | 2000-11-07 |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《中国科学(E辑)》浏览原始摘要信息 |
|
点击此处可从《中国科学(E辑)》下载全文 |
