模糊树语言与模糊树文法的等价性

考虑采用正则表达式,有限自动机和文法来描述,提出了模糊树正则表达式的概念,得到了模糊树正则语言的可识别性,并证明了模糊树语言是正则的充分必要条件,这为进一步讨论模糊树自动机奠定了基础.     

时间自动机与信号自动机的互模拟算法

基于时间自动机的验证工具已被广泛应用于实时系统模型验证。信号自动机为一类实时系统建立了比时间自动机更适合的模型,但是它还不能用于实际的实时系统模型验证,因为没有验证算法可用。把信号自动机验证问题归约到了时间自动机验证问题：证明了两种自动机具有相同的识别语言能力,证明了二者具有双向模拟关系,并在此基础上提出了线性的互模拟算法。把互模拟算法和已有的时间自动机验证算法结合起来,就得到了信号自动机的验证算法,从而解决了对信号自动机模型的验证问题。     

描述高维崎变模式的有效方法——Fuzzy 树文法

为了有效地描述带有Fuzziness 的高维模式,本文首先提出了Fuzzy 树文法与Fuzzy 树自动机的概念,进而研究了二者的关系.即:对每个Fuzzy 树文法,都可以构造与之等价的Fuzzy 树自动机.从而达到了自动识别Fuzzy 树语言的目的.     

二维二方向有限自动机的识别能力研究

研究了3种有限自动机,即二维二方向的确定型、非确定型以及Las Vegas有限自动机.证明存在语言能被二维二方向的Las Vegas有限自动机识别,但不能被相应的确定型有限自动机识别;存在语言能被二维二方向的非确定型有限自动机识别,但不能被相应的Las Vegas有限自动机识别.研究结果表明,二维二方向的Las Vegas有限自动机所识别的语言真包含确定型有限自动机所识别的语言;二维二方向的非确定型有限自动机所识别的语言真包含Las Vegas有限自动机所识别的语言.     

Fuzzy树自动机的等价性

在给出模糊树自动机概念的基础上,讨论了模糊树自动机与传统字符自动机、模糊有限自动机相类似的性质,即指确定性模糊树自动机与非确定性的模糊树自动机的等价性、FNBTA与FNTTA 等价,及FDBTA和FNBTA等价;这为模糊树自动机的进一步研究奠定了基础.     

树自动机理论在XML中的应用

XML的发展，引发了人们对于文档和形式语言之间关系的研究，树自动机理论重新引起了研究者们的高度重视。介绍了树自动机的概念、类型及处理方式，讨论了树自动机在XML中的应用，以XML文档有效性检验为例，实现了一个XML文档DTD树自动机，实验结果表明树自动机理论能够有效地处理XML文档。     

基于时间自动机的UML模型转换与验证研究

针对无法对UML模型进行形式化验证的问题,提出在元模型层将UML模型转换为时间自动机模型并进行验证的方法.形式化UML状态机的结构,抽象出UML和时间自动机的元模型,利用模型转换语言ATL对UML元模型和时间自动机元模型构造映射规则,实现UML模型到时间自动机模型的转换,在模型验证工具Uppaal中对转换结果进行形式化验证.最后进行实例研究,结果表明了此方法的有效性和先进性.     

语音识别中基于两层词法树的跨词搜索算法

为了在连续语音识别过程中充分并且高效地使用上下文相关声学模型,提出了一种新颖的基于两层词法树的跨词搜索算法.采用两层词法树来表示搜索空间,解决了现有单层词法树的规模爆炸问题,使其有能力在词边界搜索中高效地使用上下文相关声学模型进行匹配,充分发挥上下文相关声学模型较好地描述协同发音现象的能力.实验结果表明,与词内搜索算法相比误识率平均下降60%,搜索时间达到实时,证明基于两层词法树的跨词搜索算法具有很好的识别性能.     

基于神经树的时间序列预测

提出了一种新的神经树模型来进行时间序列预测。采用语法引导的遗传编程来进化神经树的结构以建立一个时间序列预测模型,并把它和基于神经网络的时间序列预测模型的性能进行比较,结果显示本文提出的神经树时间序列预测模型较神经网络模型有更高的可信度。     

基于角色的访问控制Petri网及协商树模型

针对基于角色的访问控制自动机等模型存在的缺陷,对Petri网进行了改进,并将改进后的Petri网应用于基于角色的访问控制中,实现了基于角色的访问控制Petri网.在角色转换过程的条件控制中,提出了协商树的方法,描述双方证书协商、形成协商树、满足角色转换条件、使角色转换得以实现的过程,实现了较为完整的基于角色的访问控制Petri网.     

一种时序数据局部相关对象聚类算法

针对高维时序数据中局部相关模式的聚类问题,建立了一种基于相关子模式的spCluster模型,讨论了该模型与平均平方残值的关系.并以此模型为基础,提出了适用于时序数据的确定性双聚类算法sp-TSC,该算法首先利用spCluster模型将局部相关的数据对象符号化,然后将字符序列插入到泛化后缀树中,利用后缀树的性质避免了穷举局部相关子模式的各种组合,有效减小了搜索空间,从而可以在数据矩阵尺寸的线性时间内发现全部最大δ-spCluster.理论分析和实验表明,该算法是高效可行的.     

基于KMP算法的有限自动机的确定化

一般非确定有限自动机转化为确定的有限自动机,其时间复杂度是指数函数级.对于小规模的,以输入串为识别语言的非确定的有限自动机,可采用本文介绍的方法加以确定化,其效率有极大的提高.     

一种时间自动机时钟离散化算法

稠密时间自动机被广泛应用于实时系统自动验证.然而其在补操作下不封闭,因而导致多种线性实时性质不可验证.离散时间自动机虽不存在此问题,但该模型表达能力偏弱.因此,提出了一种时间自动机时钟离散化算法,结合时钟物理约束因素,证明了新方法可有效解决上述问题.     

基于后缀树的图像识别研究

分析了后缀树在一维和二维字符串处理方面的优势．以后缀树为索引，将后缀树和最低公共祖先问题相结合，提出了一个在仅考虑平移变换操作的条件下．进行图像精确识别的算法，并从时间复杂度上证明了其优于传统的二：维精确模式匹配算法。     

基于树自动机的网页数据抽取

为了自动将数据从HTML网页中抽取出来,采取树自动机推断方式进行数据抽取.核心思想是将样本网页转化为二叉树并构建出能够接受这些网页二叉树的树自动机,利用所得到的树自动机对待抽取网页的接受和拒绝状态进行数据抽取.该方法充分利用了HTML文档内在的树状结构,设计了简单方便的样本网页标注形式.实验表明,该方法的抽取性能在查全率和F值方面优于其它的一些数据抽取方法.     

模糊树自动机的积与覆盖

给出了模糊树自动机的全直积、限制直积、级联积和圈积以及覆盖的定义,讨论了模糊树自动机积之间的关系、模糊树自动机积之间的覆盖关系以及模糊树自动机的积与覆盖它们的模糊树自动机的积之间的覆盖关系.     

Rees定理在稠密正规语言中的一个应用

称可被有限自动机识别的语言为正规语言 .字母表 A上的语言 L称为稠密的 ,如果 A*中每个字都是 L中字的子字 .不能写为其他字的幂的非空字称为本原字 ,不是本原字的非空字称为非本原字 .Shyr等提出如下猜想 :每个稠密正规语言中含有非本原字 ,本文利用 Rees定理给出这一猜想的证明     

基于关系树的知识查询算法研究

在关系模型的语义网知识表示基础上,将关系模型转换成关系树.基于此关系树模型,提出一般直接知识的正向.逆向知识查询算法,对不能直接查询的知识,进一步提出隐含知识查询算法,结果表明,提出的查询算法能有效地解决基于知识库知识查询的相关问题.     

一种基于时间自动机网络的实时系统形式化验证方法

介绍了时间自动机形式模型,在此基础上给出了时间自动机网络的形式语法和语义,然后给出一种基于时间自动机网络的实时系统形式化验证方法,并采用基于时间自动机网络的模型检测工具UPPAAL对一个经典的实时系统实例进行了验证．     

基于博弈树的概念图推理算法

提出了一种基于博弈树的概念图推理算法.该算法将封闭世界模型上的概念图推理转化为对博弈树根节点的可解性标示过程.算法采用深度优先策略,可以实现对此模型下任一个概念图或概念图集合“真值“的识别.推理结果与人类思维相一致.