基于状态可达图的离散事件系统时态性质分析

离散事件系统的许多重要性质可用时态逻辑方便、直接和简明地进行描述，系统的性质分析可转化成时态公式满足关系的判定。基于状态可达图，给出了有限系统时态特征的判定方法。

时间约束Petri网的状态可达性分析算法

时间约束Petri网是具有广义时间约束的一类Petri网。时间约束的引入使TCPN′s的演化与系统每一时刻的状态都密切相关 ,导致网的动态复杂性。目前有关TCPN′s状态可达性的研究仅局限于一些较简单的网。进一步研究了TCPN′s,给出了更一般的可达性分析方法及变迁可调度决策算法。

基于结构无竞争Petri网的DEDS的状态可达性可控性及其控制

本文给出了依靠代数递推计算判断结构无竞争Ｐｅｔｒｉ网的状态可达性的一种方法；提出了动态子网的概念，提高了判断速度；研究了结构无竞争Ｐｅｔｒｉ网的可达状态控制问题。

SIP软交换系统对话状态可达性的研究

针对SIP软交换系统提出了在同一个会话中点到点终端对话的状态可达性模型。根据SIP及SIP扩展协议,并结合stateless和stateful的模式,研究SIP终端间三方通话时的对话状态可达性模型,通过应答前传送来检证三方通话的对话状态可达性模型。

车辆跟随控制策略的状态可达集建模及验证方法

车辆动态行为的不确定性会造成跟随车辆控制的不确定性.传统的车辆跟随控制方法只是针对车辆的单一行为动态的不确定性进行建模,无法遍历车辆所有可能的控制输入,因而,既无法一次性提供跟随策略下完整的可行控制方案,也不足以在理论上保证对策略安全检测的可信性.为此,提出车辆跟随控制策略的状态可达集建模及验证方法.该方法将控制策略转换为能用可达集计算和表征的多级安全判定事件,利用随机可达集的状态遍历特征描述车辆控制输入的不确定性,通过对可达集交集的判断,辨识所有初始条件对应的危险与安全控制行为,为驾驶员提供完整的可选择控制方案;然后利用马尔科夫链逼近可达集,近似表达车辆行为的不确定性,依据驾驶员行为习惯统计验证策略的安全性,实现对控制策略的有效建模分析.实验结果表明,所提出的建模及验证方法不仅可以完备地表征车辆不确定行为,提供交通情形中跟随策略相应的完整控制方案,也可实现对策略安全性的精确验证.

不确定规划中状态循环可达关系的求解方法

在不确定规划领域中,不确定状态转移系统求规划解常常会搜索大量无用的状态和动作,造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算,为系统提供引导信息。以非循环可达关系为基础,定义矩阵的计算规则,使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等,并设计了求循环可达关系的算法,且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系,在求规划解的过程中可以删除大量无用的状态动作序偶,降低问题规模,提高求解规划问题的效率。

基于可达最佳状态标准的叶尔羌河健康评价

为了有效保护和管理干旱区内陆河流,以叶尔羌河卡群—艾力克塔木河段为研究对象,提出"以可达最佳状态为标准"的河流健康评价标准;基于压力-状态-响应模型建立了包含24项指标的河流健康评价指标体系;构建了基于突变级数法的河流健康评价模型,进行河流健康评价研究。结果表明:评价现状年2015年该河段目标层突变级数为0.95,河流健康综合评价等级为Ⅲ级,处于亚健康状态,即河流健康为由健康向不健康过渡的预警状态。评价结果与实际情况基本符合,河流健康生命已受到威胁,河流健康维护工作势在必行,维护河流健康的关键是满足河道生态基流保障率,提高河道外用水尤其是农田灌溉用水效率,以及提高流域管理机构河流综合治理水平和水资源优化配置效率。

不确定规划中循环可达状态信息的维护

动态环境下,动作执行的不确定性会因外部因素存在变动,因此将导致不确定系统中的状态可达关系可能发生改变。为解答这一问题,论文对信息传递法中状态之间可达关系的更新方式进行改进,提出一种新的状态可达关系的维护算法。该算法将变更的状态之间可达关系与原可达矩阵对比,利用邻接矩阵中对应可达信息对变更后状态的可达信息进行修改,然后通过状态之间信息传递,求解不确定系统中局部状态可达关系,从而避免了更新过程中的重复计算。实验结果表明,该方法在运算时间上要优于重新利用信息传递法来维护系统的状态可达关系。

一种基于MDDs的可达状态的算法研究

以固定点为数学基础,多值决策图(Multi-Valued Decision Diagrams,MDDs)为存储结构来实现系统可达状态空间建立的饱和算法在异步系统的模型中显示其良好的空间和时间效应。对该算法的理论和实现方法进行详细的阐述和分析,提出通过对当前事件中的扩展链的预先判断,修改原饱和算法来实现取消无扩展链的事件的函数递归调用、新节点的内存空间的申请与回收,达到提高算法的时间和空间效率;并从理论推理和实验上进行验证。

开放Petri网可达状态求解系统的开发与实现

Petri网模型是理论计算机科学包括自动机模型和形式语言理论的一个分支,具有自然、直观、简单易懂等特点。开放Petri网是Petri网的一种扩充,在并行模型分析,协议的验证,自动控制等方面有广泛的应用。该文的主要工作在于开发一个可以生成开放Petri网的软件,并能够求解其所有的可达状态,最后通过这样一个软件来研究开放Petri网的可达状态总数随网的规模变化和初始Token数变化而变化的情况。我们得到的结论是在这两种情况下可达状态数都是呈指数增长的。

不确定规划中非循环可达关系的求解方法

对一个不确定状态转移系统求多个规划问题,那么获得不确定状态转移系统的状态可达关系可以方便求解规划问题,减少冗余计算,建立系统的引导信息。提出一个关于矩阵求不确定领域的状态可达性关系的方法,主要思想是以矩阵乘法来模拟状态转移系统中状态转移,对不确定动作带来的扩散和确定关系带来的聚合进行了统计和处理,从而获得状态可达信息。证明了方法的正确性和有效性。在不确定规划中确定了状态之间的可达性关系,可以在求规划解时删除对规划没有用的状态节点和状态动作序偶;选择能到达目标节点的状态节点和状态动作序偶;进行启发式正向搜索;减少大量冗余计算;提高求解效率。

混合动态系统SPN的可达性分析

根据混合动态系统SPN(StochasticPetriNets)模型的运行规则,给出了几种典型结构(串行结构、并行结构、冲突结构)中变迁的可激发以及可激发成功概率的计算方法,在此基础上,计算出托肯沿几种基本路径(简单串行路径、简单并行路径、简单Fork/Join路径)从起始库所到达终止库所的可达概率,同时从宏观状态的角度构建了该SPN模型的状态可达树,通过可达树可以判断状态间的可达性并计算可达概率。

利用状态缓存的时序等价性验证算法

为了提高时序电路的等价性验证速度,提出一种改进的基于寄存器匹配的验证算法.除了利用原像计算避免误判之外,该算法还将可达状态和不可达状态引入到验证过程中.将仿真过程中从初始状态可以到达的状态记录为可达状态,将验证过程中确认不能从初始状态到达的状态记录为不可达状态,利用它们减少验证过程中的原像计算.基于mcnc91电路的实验数据表明,该算法有效地减少了验证时间.

基于UML状态图和基本Petri网生成测试用例

结合UM L状态图和Petri网提出了一种生成测试用例的方法。将UM L状态图转换成对应的EN—系统模型,利用EN—系统的性质检测并排除UM L状态图中的不可达状态和事件的冲突和冲撞;再应用与合理的UM L状态图对应的EN—系统生成可达状态图,利用可达状态图生成测试用例。该方法一方面可以很好地实现并行子状态的嵌套问题,避免了将并行的UM L子状态展平成EFSM时引起的状态爆炸问题;另一方面,由于测试用例的覆盖标准是基于可达状态图的基路径、事件和可达状态覆盖,所以还很好地解决了对系统的不同测试要求和状态的可达性问题。

改进的状态空间模型遗传算法及其全局收敛性分析

基于状态空间模型遗传算法(GABS)是一种新型实数编码进化算法,在工程优化问题中取得良好的应用效果.针对GABS缺乏有效的数学模型及理论依据,研究并建立了GABS的吸收态马尔可夫过程模型,从可达状态集的角度对GABS进行分析并证明GABS不是全局收敛的.基于此提出了一种扩张可达状态集的改进型GABS(MGABS),改进方法的两种变异策略不仅扩张了算法的可达状态集、提高了种群多样性,而且加快了算法的收敛速度与精度,并证明了MGABS具有全局收敛性.最后利用经典测试函数验证了其综合性能明显优于其他3种算法,为算法在工程中的应用提供了理论依据.

面向程序验证的并行程序状态空间态约简技术综述

程序验证是保证程序安全性的重要手段。随着采用多核技术的硬件环境日渐普及,越来越多的软件正通过转向基于共享内存的并行程序模型来充分利用现有的计算资源。各线程在并行执行时通过共享内存的访问互相干扰执行状态,导致可能执行路径数成几何级数增长,进而产生可达状态空间爆炸问题。由于验证并行程序安全性主要通过分析程序可达状态来实现,因此,对并行程序可达状态空间的约简是决定并行程序验证效率的关键因素。首先对面向并行程序验证的并行程序可达状态空间约简方法进行了分类,然后对各类可达状态空间约简方法分别进行了分析和总结,最后指出了当前存在的问题和未来解决这些问题的研究方向。

概率布尔控制网络的可观性分析

概率布尔控制网络的转移矩阵的不确定性,使得其可观和可控性分析和状态估计更为困难。主要研究了概率布尔控制网络的可观性问题,并在此基础上给出了判断系统可观的条件,以及计算系统初始状态向量的方法。首先,根据系统的可达状态集,定义系统的可区分和不可区分状态,并给出d步可区分的概念以及其判断的充要条件。其次,根据概率布尔控制网络的输出和系统模型,得到系统的概率初始状态集合。接着,在此基础上给出概率布尔控制网络的强可观和弱可观的定义。同时,计算系统初始状态向量,并且给出判断系统是否可观的定理;最后,通过一个算例说明了所提方法的有效性。

基于时间Petri网的嵌入式系统构件建模与能耗分析

现有软件能耗分析方法主要研究算法级和指令级能耗,对于软件体系结构级的能耗研究较少。为此,从嵌入式系统的软件体系结构出发,在传统Petri网的基础上加入价格和时间标签,建立价格时间Petri网。通过价格时间Petri网构建软件构件和连接子能耗模型分析系统软件能耗,并提出最小能耗可达路径算法降低系统执行能耗。实验结果表明,该模型测得的实际能耗结果与预期结果误差较小,并且能降低系统整体能耗,提高资源利用率。

FPGA组合逻辑程序的Petri网建模方法

针对现场可编程门阵列(FPGA)组合逻辑程序,提出其普通Petri网建模方法.首先,将状态变量描述为库所对,程序中的逻辑运算描述为变迁,从而将系统程序转换为一个普通Petri网结构;然后,根据Petri网的动态分析性能,给出系统状态可达图的计算方法,实现了状态可达图等价描述FPGA组合逻辑系统运行过程.研究结果表明:该Petri网能够准确地描述变量间的逻辑关系,提出的方法可以为FPGA组合逻辑程序的形式化设计和验证提供建模依据.

基于时间Petri网的实时嵌入式软件系统安全性分析

本文介绍了时间Petri网模型在实时嵌入式软件系统的安全性分析中的应用,并通过一个实例介绍了时间Petri网的动态分析法,最后给出了相应方法的具体措施。