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

• 作者: 蒋昌俊
• 来源期刊: 中国科学E辑
• 学科: 工学
• 关键词: Petri网 同步合成 合法发射序列 判定算法 NP完全问题 多项式复杂性
• 年，卷（期）: 2002,（1）
• 页码范围: 116-124
• 页数: 9页
• 分类号: TP3
• 字数: 5279字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9275.2002.01.015

摘要

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