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

摘要：

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

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

所属期刊栏目：32

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金69973029,69933020;国家自然科学基金60125205;国家重点基础研究发展计划973计划G 1998030604;全国高等学校优秀博士学位论文作者专项基金199934;上海市教委"曙光计划";上海市重点基础研究项目;高等学校优秀青年教师教学科研奖励计划;山东省优秀中青年科学家科研奖励基金

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：116-124