交互复杂度——面向网络计算的复杂度指标

随着网络计算的盛行 ,计算问题的解决越来越倾向于通过分布在网络上的服务的交互来完成 ,研究问题在交互意义上的复杂度显得日益重要 提出了以交互为基本要素的通用计算模型———交互积 ,在此基础上提出了算法的交互复杂度指标 ,并初步探索了交互复杂度和时间复杂度之间的关系 利用 3 GIP的通用性 ,可以降低网格系统的成本和提高好用性 ,而交互复杂度可以作为网格上问题解决方案的评价指标 。

基于线性时态逻辑的Petri网模型检测

Petri网是一种重要的数学工具,它能有效地对并发系统进行描述和建模。线性时态逻辑LTL则是描述和验证并发系统特性的一种重要的形式化工具,它能方便准确地描述并发系统的重要性质,如安全性和活性。文章深入描述了线性时态逻辑、Büchi自动机、Petri网和同步积之间的内在联系,并探讨了基于线性时态逻辑的Petri网模型检测策略。与其它方法比较,这种模型检测的策略结合了线性时态逻辑和Petri网模型的不同优点,增强了Petri网的模型分析和验证能力。最后,通过对一个并发系统形式化的模型检测分析,验证了相应的结论。

基于随机无穷自动机的多功能雷达辐射源识别方法

针对基于随机上下文无关文法(SCFG)建模的多功能雷达(MFR)辐射源识别问题,提出了一种基于随机无穷自动机(SISA)的MFR辐射源识别方法。在文法建模的基础上,对"水星"MFR控制模块文法产生式和系统特征文法产生式进行重新构造生成SCFG,利用SCFG构造随机无穷自动机作为识别器,从而实现对测量辐射源的识别。通过理论分析和实验仿真得出:该方法能实现对MFR辐射源的识别;在一定范围内,通过增加文法产生式个数,可以提高平均识别率,且识别性能优于通过SCFG构造的随机下推自动机(SPDA)。实验结果表明了该方法的正确性和有效性。

基于自动机的概率计算树逻辑验证方法

根据带有随机特征的复杂信息系统性质验证的需求,针对离散概率回报模型的分层直到公式,提出一种性质验证分析方法。在综合各种离散随机逻辑的基础上,使用一种同时具有迁移回报及迁移步区间表达能力的概率计算树逻辑表示系统模型的分层直到路径公式性质,使用自动机技术建模路径公式,通过构造积模型完成模型与自动机的同步演化,基于积模型给出相应的状态概率满足算法。实例结果验证了该方法的可行性和有效性。

最大乘积型Fuzzy上下文无关文法与下推自动机

为了扩大现有研究的应用范围,基于最大乘积型Fuzzy文法与自动机引入了最大乘积型Fuzzy下推自动机的概念,并讨论了最大乘积型Fuzzy上下文无关文法与最大乘积型Fuzzy下推自动机的关系.研究表明,当且仅当最大乘积型Fuzzy上下文无关文法产生的语言集能被最大乘积型Fuzzy下推自动机接受时,能达到自动识别最大乘积Fuzzy上下文无关语言的目的.

基于乘积张量算法的模糊离散事件系统自动机组合及应用

对已有的状态转移规则进行分析与比较,结合最大乘积状态转移规则提出一种基于乘积张量的自动机组合方法,并结合实例证明了基于乘积张量的模糊离散事件系统自动机状态转移定理.结果表明,在进行自动机组合时,各自动机先进行状态转移再组合与先进行组合再状态转移得到的结果是一致的,2种不同的运算顺序在运算复杂度及运算量方面具有相对优越性,但前一种运算顺序在组合复杂度及运算时间方面都要比后一种更为优越.

有限自动机定义函数的线性本原圈积分解

本文讨论有限自动机显表出定义函数ｆ的线性本原圈积分解问题．在该圈积分解之下，函数ｆ被表成线性外函数因子ｆＬ与线性本原内函数因子ｆＮ的圈积，这里函数ｆＬ定义了一个线性弱可逆有限自动机ＭｆＬ，而函数ｆＮ定义了一个非线性有限自动机ＭｆＮ且其不能再分解成一非平凡的线性外函数与一非线性内函数的圈积．本文证明了一函数ｆ的任两线性本原内因子互为对方的线性本原内因子，从而证明了函数ｆ的线性本原圈积分解的唯一性．本文所给出的函数ｆ的线性本原圈积分解比此前已有的ｆ的相对（ｔ０，Ｔ）圈积分解能进一步降低求ｆ定义的有限自动机Ｍｆ的弱逆Ｍ＊ｆ的复杂性，其可应用于有限自动机公钥密码体制的密码分析中．

正规集的若干性质

正规集是对许多语言理论起核心作用的一类语言，研究正规集的性质有助于有限态文法的文法推断和句法分析的研究以及正规集的自动识别。在文献［１］的基础上对正规集的一些重要性质进行了详细讨论，完善了正规集的理论。

线性时序逻辑约束下的滚动时域控制路径规划

针对有限确定性系统中的路径规划问题,本文提出了一种线性时序逻辑约束下的在线实时求解滚动时域控制的新方法。该方法将滚动时域控制方法和满足线性时序逻辑公式的策略相结合,控制目标是在满足高级别任务规范的同时,使收集的累积回报值最大化。其中,在有限时域内的每个时间步长上局部优化回报值,并应用当前时刻计算获得的最优控制序列。通过执行适当的约束,保证控制器产生的无限轨迹满足期望的时序逻辑公式。而且,由于地势影响因子的引入,所建议的方案更接近于真实情况。仿真实验结果验证了文中提出方法的可行性和有效性。

改进的自推动粒子模型与群体行为研究

采用原胞自动机对自推动粒子模型进行改进,分析了在低密度空间、中等密度空间以及高密度空间3种情况下,大众生产系统生产者的决策影响因素。研究表明,在中等密度空间,大众生产系统中生产者的决策突变不仅与生产者的密度相关,还与系统的开放性以及智能粒子的更新速度密切相关。进一步地采用复杂网络对自推动粒子模型进行改进。结果表明,当外部影响较小时,网络拓扑结构对群体一致决策无太大影响,系统稳定时群体的一致决策方向与外部初始条件相关;当外部影响较大时,在满足外部影响与网络拓扑结构一定关系的条件下,系统中自推动粒子的群体决策与基于原胞自动机的结果相似。根据大众生产合作网络的无标度特性分析了在动态增长无标度网络中的稳定结果,得出当γ>3时动态增长的网络系统中自推动粒子的群体行为选择仍然具备突然改变方向的性质。

基于时序逻辑的复杂环境下无人机运动规划算法

本文主要考虑基于时序逻辑的无人机运动规划问题。一般地,解决该问题的算法包括两个阶段:上层综合阶段生成一条可行的离散规划;低级综合阶段结合离散任务规划设计无人机的控制输入。但是当第一阶段失败时,即线性时序逻辑(LTL)任务在当前环境中无法实现时,我们希望系统能够进行一定的调整。本文提出了一种任务重规划算法,在深入理解模型检查原理的基础上,利用初始任务自动机生成一个松弛乘积自动机,进而获取有效的离散任务规划;同时设计一个自动机的权重函数,确保该规划在最小程度上违背初始任务所提出的约束。本文提出的重规划算法解决了时序逻辑在复杂环境中无法实现的难题,扩大了时序逻辑在无人机运动规划中的应用范围,同时增加了系统的鲁棒性。

金属表面腐蚀损伤形态演化规律研究

针对金属材料在环境作用下容易形成腐蚀损伤而致其力学性能降低的问题,采用元胞自动机方法,通过定义元胞规则,以氢标电极电位作为材料特性参数,定义铝和铁两种金属的溶解概率。研究两种材料在不同的温度和相对湿度腐蚀环境下,腐蚀表面形态演化和腐蚀产物形成规律。结果为研究金属搭接件在环境作用下的枕垫效应提供了理论依据。

适用于演化过程建模的通信膜演算

针对膜计算类形式化方法无法描述建模完成的系统的演化问题,提出了一种适用于演化过程建模的通信膜演算。该演算在已有的膜计算类形式化方法的基础上,通过在定义中添加规则的传递等反应规则,使得建模完成的系统可以根据演化需要发生变化,解决了膜计算类形式化方法不适用于对系统演化这一普遍存在的问题,即进行形式化建模的问题。同时利用自动机理论对通信膜演算的性质进行分析,分析了通信膜演算适用于演化过程建模的原因。并利用通信膜演算对一种软件产品线的特定演化过程进行了形式化建模,建模结果表明通信膜演算适用于对演化过程的形式化建模。

一类特殊形式的Fuzzy正则语言注记

对一类特殊形式的Fuzzy正则语言作了一定的讨论,得到了两个重要定理,为进一步研究Fuzzy正则语言与Fuzzy有限状态自动机的关系奠定了基础.

Fuzzy正规集合与Fuzzy右线性文法的关系

在文献[1]的基础上,对Fuzzy正规集合和Fuzzy右线性文法之间的关系作了进一步的探讨,证明了Fuzzy正规集合的右线性可表示性,为进一步研究Fuzzy正规集合与Fuzzy有限状态自动机的关系提供了一种新方法。

语法图到产生式的自动转换

语法图和产生式是对语法的两种描述形式，一般在语言设计时采用语法图描述，在语言实现时采用产生式描述，从语法图到产生式的自动转换是编译程序自动化课题内容的一部分。作者对语法图的图符号给出了确切的定义，并提出了连接关系图的概念，从而把语法图和有限自动机联系起来，以有限自动机为过渡形式，使语法图到产生式的自动转换机理清晰，实现方便。不仅给出了语法图到产生式的转换原理，还给出了考虑优化的转换算法和具体实施步骤例，该方法在实际使用中有很好的效果。