数据传送进程的符号互模拟*

本文提出数据传送进程的符号迁移语义，引入符号互模拟的概念，证明了两个进程在传统意义下互模拟当且仅当它们符号互模拟．由于无穷域上的数据传送进程的传统迁移图是无穷的，而其中相当一部分的符号迁移图是有穷的，文章的结果为在有穷时间和空间内判定这类进程的互模拟关系开辟了可能性．     

线性函数方程组的展开式解

本文给出了函数方程组的展开式基本定理及其有穷形式,并用此基本定理证明了几个关于二元线性函数方程组的解的展开定理,同时举了几个应用这些定理解函数方程组的具体例子。     

动态故障树的边值多值决策图分析

动态故障树分析对于复杂系统来说是一种重要的可靠性分析技术,但是二叉决策图等传统模块化方法存在严重的状态空间爆炸问题.本文系统介绍了边值决策图的动态故障树分析方法,其中边值多值决策图相对于其它现有的决策图具有更紧凑的表示函数,通过状态数的缩减,缩短了计算时间,有效缓解状态空间爆炸问题.实例证明了边值多值决策图在多状态系统和多功能系统中使用的方法和优势.     

数据传送进程的符号互模拟

本提出数据传送进程的符号迁移语义，引入符号互模拟的概念，证明了两个进程在传统意义下互模拟当且仅当它们符号互模拟。我穷域上的数据传送进程的传统迁移图是无穷的而其中相当的一部分的符号迁移图是有穷的，章的结果为在有穷时间和空间内判定这类进程的互模拟关系开辟了可能性。     

基于最大不动点模型的描述逻辑系统FLε的有穷基

研究了描述逻辑的有穷基问题,分析了有穷基在描述逻辑中的重要意义及其研究现状,并研究了形式概念分析中的属性蕴舍和Duguenne-Guigues基问题.利用形式概念分析中Duguenne-Guigues基存在的证明结果,在F.Baader工作基础上设置了描述逻辑的描述背景,重新定义了描述背景下的属性蕴含,证明了带循环术语的描述逻辑系统FLε存在最大不动点语义(greatest fixed-points,gfp)模型,给出了带循环术语的描述逻辑系统FLε在最大不动点模型下的有穷基的存在性定理,并证明有穷基的可靠性和完备性.描述逻辑有穷基可以帮助知识工程师构建一个更适用于推理的描述逻辑知识库.     

基于迭代切距离原型学习算法的步态识别

作为唯一远程生物认证技术,步态识别一方面越来越受到人们的重视,提出了很多相应的算法,另一方面,它又面临着很多挑战,其难点之一是如何从多帧步态中有效地提取步态特征,针对此问题,并基于步态能量图(GEI)在步态特征表示上的效果,提出了一种迭代切距离原型学习算法,假定各人的步态分布在不同流形上面,首先用切距离改进步态能量图的定义,进而用迭代的方法来解一个最优解问题,从而学习出步态原型图,再通过PCA对步态原形进行特征提取,最后进行识别,证明了该方法的收敛性,实验结果表明所提出的方法取得了比GEl更好的识别率,并证明了步态流形的假设的合理性.     

三维阵列细胞结构图的性质及其定理

本文研究了三维阵列图的算法,证明了若干性质和定理。应用它可以对任意有穷的K~3阵列的细胞结构的各种路径进行自动分析。     

不确定图上期望最短距离的计算

研究了不确定图上的最短距离问题,提出了期望最短距离的概念,证明了该问题不存在多项式时间的算法.为了解决该问题,使用了随机采样技术获得不确定图的一些可能世界,在每个可能世界上计算有穷的最短距离,最后计算出平均值作为期望最短距离的估计值.为提高计算效率,使用了过滤条件来减少采样过程中采样的边数从而加快随机采样.在此基础上,提出了一种基于对称变量的、无偏的随机采样近似算法,并证明了与直接随机采样方法相比,该方法在不增加时间开销的同时能减小采样方差.通过真实数据上的实验表明,提出的算法在时间开销和采样方差上均明显好于直接随机采样方法.     

关于ω—正则语言类的一个子类的特征

为了给出本文的主要结果,首先引进了由有穷字母表∑上的ω~-语言所确定的集合∑~ω上的ω-Nerode等价关系的概念.在此基础上证明了∑上的与前缀逆相关的ω~-语言是ω~-正则语言,当且仅当由它所确定的ω-Nerode等价关系的指数有穷.从而,本文从代数、集合的角度给出了在∑上的与前缀逆相关的一类ω~-语言中,ω~-正则语言的特征.     

三维限定Voronoi网格剖分细化算法

针对分段线性复合形约束条件下的三维限定Voronoi剖分问题,提出一种细化算法.首先证明了分段线性复合形中的元素在最终生成的三维限定Voronoi网格中可表示为Power图结构;受此启发,提出了对限定线段平面片分别进行一维二维Power图细化以实现三维限定Voronoi 网格生成的细化算法,并且证明了该算法对于任意分段线性复合形收敛.最后通过实例验证了文中算法的有效性.     

基于规则的最短路径查询算法

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.     

非线性不确定系统的H∞滑模控制

对于一类具有不满足匹配条件干扰的非线性不确定系统, 定义了H_∞ 滑模控制问题Q1.通过状态变换和状态反馈以及干扰重定义, 提出了线性系统的滑模干扰抑制问题Q2. 问题Q2 可以通过解Riccati不等式得以解决. 在一定的假设条件下, 证明了可以通过解Q2 获得Q1问题的解. 最后给出了保证滑模存在的控制律. 单机无穷大系统励磁控制的计算机仿真结果表明了该方法的有效性.     

基于有穷自动机的自动信任协商策略

自动信任协商通过协商策略协调协商双方间访问控制策略、信任证的交互披露以逐步建立信任.现有的访问控制策略规则的理论表示缺乏直观性,在分析和构造策略算法时带来不便.本文将有穷自动机形式化定义与自动信任协商相结合,提出一套基于有穷自动机的信任协商定义体系,并构造有穷自动机状态转换图对相应的访问控制策略进行图形化表示,便于分析和构造协商策略.针对积极策略缺乏安全性和谨慎策略缺乏高效性的问题,提出了基于有穷自动机的协商策略,该策略在谨慎策略的基础上加入记忆链结构,以减少协商双方交互次数,提高协商效率.经证明,该策略具备完备性和安全性,并通过仿真实验证明相对于谨慎策略,该策略具备高效性.     

GPP问题的骨架分析与启发式算法设计

图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.     

压缩感知优化问题的等价表示及其目标罚函数方法

首先定义了压缩感知优化问题的一个等价表示问题,证明了这个等价表示问题的最优解也是压缩感知优化问题的最优解。然后定义了它的一个具有2阶以上的光滑性的目标罚函数,给出了一个迭代求解算法,证明了所提算法的收敛性定理。定理表明,可以通过求解目标罚函数来获得压缩感知优化问题的近似最优解,该方法为研究和解决实际的压缩感知问题提供了一个新的工具。     

一类解Stiff常微分方程组初值问题的多级隐式Hybrid方法

§1.引言 为了叙述上的简洁而又不失一般性,我们考虑Stiff常微分方程组自治系统初值问题 y′-f(y),y(0)=Y_0 (1.1)的数值解,在此假定F(y)有适当的可微性并用y(z)表示(1.1)的精确解,用y_n表示(1.1)在x=nh点的数值解。h为积分步长,记f_n=f(y_n)。 在[1]中,Dahlquist证明了A稳定的线性多步法所能达到的最高阶是2。1978年Wanner等人进一步证明了A稳定的线性方法所能达到的最高阶不能超过2q,其中q可以是多导方法的最高导数或者是Runge-Kutta方法的级数。也就是说,高阶A稳定的方法只出现在像隐式多导方法或隐式多级Runge-Kutta方法等一类方法中。本文暂只涉及     

自然语言处理中的逻辑词

词是自然语言处理中最基本的单位,在当今知识表示领域,知识图作为自然语言理解的语义模型有其独到之处。本文从语言学和逻辑学的角度,首次提出并探讨了逻辑词研究逻辑词分类及如何用知识图表示各类逻辑词的结构。对自然语言处理中研究复句和篇章的理解提供了一种新的途径。     

无圈与或图搜索的符号OBDD算法研究

与或图搜索是人工智能领域一项重要的问题求解技术.基于传统数据结构的与或图表示技术极大地限制了与或图搜索算法可求解问题的规模.在无圈与或图符号OBDD表示的基础上,给出了一种求解无圈与或图最小代价解图的符号搜索算法.实验结果表明,与 AO*算法相比,该算法可处理问题的规模有较大的提高.     

带权区间图的最短路算法

提出一个解带权区间图的最短路问题的O(nα(n))时间新算法，其中n是带权区间图中带权区间的个数，α(n)是单变量Ackerman函数的逆函数，它是一个增长速度比log n慢得多的函数，对于通常所见到的n，α(n)≤4．本文提出的新算法不仅在时间复杂性上比直接用Dijkstra算法解带权区间图的最短路问题有较大改进，而且算法设计思想简单，易于理解和实现．     

二值命题逻辑的无损求解

针对协同问题求解、协同设计等诸多领域中存在逻辑冲突的共性问题,从二值命题逻辑理论出发,研究面向冲突的无损求解(即初始解空间获取)问题.首先,提出简单合取式的扩充和Wh-析取范式等概念,在此基础上定义初始解空间,并通过提出的有效扩充概念得到初始解空间的简化表示——最简解空间,探讨了两类解空间的关系及各自的计算方法.其次,构造生成序列来辅助公式的析取化,从泛代数的角度定义了Wh-代数;提出了指数矩阵,并籍此给出了Wh-代数的等价表现形式,通过引入扩展指数矩阵构造出扩展Wh-代数.最后证明了扩展Wh-代数中的展开定理和逻辑简化定理,给出基于有效扩充的直接无损求解算法,并与提出的其他相关算法进行了对比,结果表明该算法较为理想.该研究对于协同问题求解等领域有着重要的推动作用.