关于Petri网归约问题

Petri 同归约问题是当今 petri 网研究领域的一个重要课题,本文从 Petri 网静态结构的角度出发,给出了三个层次的 Petri 网归约方法,并用代数的方法严格地证明了这些归约方法保持网的两大重要性质:活性和有界性。它们为 Petri 网的归约和分析的复杂性之间提供了一个灵活折衷的手段,能够对一个庞大、复杂的 Petri网进行不同程度的归约,以适应不同的需要。文中所给出的归约算法是基于网的关联矩阵的,具有高效,便于实现的特点。此外,本文还就多弧 Petri 网的归约问题和 Petri 网的分解问题作了简要讨论。最后还给出了哲学家用餐问题的 Petri 网新模型并对之进行归约。     

分划递推法在Hanoi塔问题上的应用

采用分划递推法通过功能归约变换,形式化推导和证明Hanoi塔问题中圆盘的移动规律,从而推导出结构清晰、可读性好、效率高、占用存储空间与圆盘个数无关的非递归算法,算法比较分析地显示出形式化推导在获得高效和正确性的算法程序中的作用.相关算法在UNIX平台下用C语言进行实现.     

一个从k-CNF到t-CNF归约的有效算法

根据极小不可满足公式的特征,对于固定的3 ≤t＜k.我们给出了一个将k-CNF公式归约到t-CNF公式的有效算法.对于给定的k-CNF公式F,t-CNF公式的转换可以在公式F的长度的线性时间内完成.     

标准当前状态不透明性与强当前状态不透明性的归约

不透明性是信息流安全中的一种重要属性,它表征了系统对入侵者保密的能力.在离散事件系统中,标准当前状态不透明性刻画的是入侵者无法根据当前的输出观测序列确定系统是否达到秘密状态．强当前状态不透明性刻画的是对每一个到达秘密状态的运行,存在一个观测等价的非秘密运行与之对应．显然,强当前状态不透明性比标准当前状态不透明性具有更强的隐秘性．针对标准当前状态不透明性与强当前状态不透明性之间的归约问题,提出一种新的转换方法,即在原系统基础上添加一些新的状态及相关跃迁,分别构造两个新的系统,证明了原系统是标准当前状态不透明的(强当前状态不透明的),当且仅当新系统是强当前状态不透明的(标准当前状态不透明的)．     

非确定有限自动机的最短D1-同步字求解

研究了非确定有限自动机的最短D_1-同步字的计算问题。针对这种自动机定义了D_1W问题及其参数化版本问题p-D_1W和最优问题shortest-p-D_1W,证明了p-D_1W和shortest-p-D_1W分别属于para-NP和para-DP。利用均匀分布模型随机生成大量的非确定的有限自动机进行实验,结果表明:在定长的参数下几乎所有随机产生的自动机实例都不是D_1-可同步的,一旦将自动机上每个状态和字母的变迁函数的像数量限制在2以内,会出现少量的D_1-可同步的自动机,且绝大多数最短同步字长不超过状态数的2倍。     

数据挖掘中基于信息熵的自适应聚类时间维度归约

数据归约作为一种数据挖掘中常采用的数据前处理技术,能够有效地提高数据分类的效果,对于时间序列数据,时间维度归约是时序数据挖掘最常用的数据归约技术。以单变量时间序列作为研究对象,提出并实现了一种基于聚类的时间维度归约方法。通过实验表明,该方法能够有效地减少数据维度,有效压缩数据并提高数据挖掘的分类准确率。     

3-状态复杂设备网络系统可靠度计算的PATH一拆法

利用3-状态设备网络可靠度计算的归约定理，结合Ruger给出的技术，我们得到了计算复杂设备网络2-终端可靠度的一个新算法，算法具有易于计算机上实现，占用计算机存储空间小，也容易手工计算的特点。     

第五代计算机及其认知逻辑方法

计算机的发展正在从顺序控制流逻辑方法飞跃进入第五代的认知逻辑方法。需要第五代计算机解决的一个关键问题是NP问题。NP机器的双语言结构与人脑的感-知双重结构相同。北大未名生物工程集团有限公司生物智能技术研究组根据人脑的结构和功能提出一套认知逻辑形式语言理论,并根据认知形式语言制成一个NP机,命名为“未名机”。未名机正在进行NP问题的多项式时间测试。如果能解决NP问题,未名机将为第五代计算机提供逻辑实施方法。     

非自治二阶系统周期解的存在性

将鞍点归约方法应用于非自治二阶系统,得到了非自治二阶系统在次线性增长条件下的周期解的存在性定理.