用Cellular Automaton模型方法模拟二元合金枝晶生长

研究并针对CellularAutomaton凝固组织模拟方法模型的物理本质、数值计算方法以及在凝固微观组织模拟中的应用进行了探索。并利用CellularAutomaton凝固组织模拟方法,求解了Al-4.5%Cu等轴晶枝晶生长。

树形偏序自动机的同步问题

对于给定的自动机,能将所有状态都转换到同一状态的输入字被称为该自动机的同步字.有同步字的自动机称为同步自动机.同步自动机已广泛应用于系统测试、编码、工业自动化、机器人技术及生物计算等领域.同步自动机研究的基本问题是自动机的同步问题(含同步性判定问题和同步字查找问题),最具挑战性的课题是证实或证伪关于同步自动机最短同步字长度的Cerny猜想.偏序自动机是具有一个相容偏序结构的自动机.同步自动机的研究从理论上可以归结到同步偏序自动机的研究上,因此,Cerny猜想成立当且仅当其对所有的偏序自动机都成立.现有的研究工作表明,Cerny猜想只对于一些结构较为特殊的偏序自动机类,包括单演自动机、广义单演自动机以及有界偏序自动机是成立的.作为偏序自动机的另一类特殊情形,本文研究关于树形偏序自动机的同步性检测问题,同步字查找问题以及Cerny猜想,主要贡献包括:讨论了树形偏序自动机与现有的几类偏序自动机之间的关系,说明了树形偏序自动机包含所有单演自动机和有界偏序自动机,并且不同于广义单演自动机类;给出了树形偏序自动机的同步性判定和同步字计算方法,特别地,证明了Cerny猜想对树形偏序自动机成立;设计了树形偏序自动机的专用同步算法,该算法的时间复杂度低于通用的自动机同步算法,且对任意n-状态同步树形偏序自动机都可以找到长度不超过(n-1)^(2)的同步字.

一种入侵检测系统的模式匹配算法

提出了一种基于后缀树自动机的模式匹配算法,匹配中应用后缀启发机制进行启发跳跃,忽略不必要的比较。实验表明,该方法与传统模式匹配方法相比能有效地加快模式匹配的速度,提高入侵检测效率。

XML自动机的构造及实用化研究

XML是目前已被广泛采用的WWW上信息交换和表示的技术之一 ,被称为Internet时代的通用数据格式 .该文首先针对现有的XML语法进行了抽象及封闭性分析 ,得到了扩展XML语法 ,接着提出了一种XML自动机的概念 ,证明了它与扩展的XML语法等价 ,而且具有“并”、“交”、“差”和“补”运算下的完全封闭性 ,然后开发了一个分析器 ,对由此扩展语法生成的对象进行分析 。

一种基于文档模式的GML压缩方法

GML已成为地理空间数据编码的事实标准.GML文档一般体积庞大,存储和传输时占用巨额资源.提出了一种基于文档模式的有效GML压缩方法,通过用文档推导出的模式验证文档本身,对树自动机的状态转换路径进行比特编码,对坐标数据增量编码,实现GML文档压缩.对真实GML文档的压缩实验表明,所提出方法的压缩率优于通用文本压缩器(gzip和PPMD)、主要高性能XML压缩器(XMill,XMLPPM和XWRT)以及现有GML压缩器GPress.

树自动机的同余与同态及其语言

从代数的角度出发研究树自动机的同余与同态,得出树自动机的同态基本定理和同构基本定理,进而研究它们之间语言的相关性质.

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

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

使用事件自动机规约的C语言有界模型检测

提出使用事件自动机对C程序的安全属性进行规约,并给出了基于有界模型检测的形式化验证方法.事件自动机可以规约程序中基于事件的安全属性,且可以描述无限状态的安全属性.事件自动机将属性规约与C程序本身隔离,不会改变程序的结构.在事件自动机的基础上,提出了自动机可达树的概念.结合自动机可达树和有界模型检测技术,给出将事件自动机和C程序转化为可满足性模理论SMT(satisfiability modulo theory)模型的算法.最后,使用SMT求解器对生成的SMT模型求解,并根据求解结果给出反例路径分析算法.实例分析和实验结果表明,该方法可以有效验证软件系统中针对事件的属性规约.

基于改进C5.0的元胞自动机模型研究——以土地利用问题为例

元胞自动机模型是通过局部的相互作用及变化来模拟全局的变化,是复杂结构来源于简单系统的重要体现。元胞自动机模型的核心是转换规则的获取,获取转换规则的方法有多种。建立一种基于改进C5.0决策树的元胞自动机模型,基于属性值的相似性对C5.0决策树算法进行改进,以期提高元胞自动机的模拟精度,该模型适用于多种复杂系统的模拟问题研究。最后以土地利用问题为例演示了模型的应用。

边界跟踪自动机与围线树结构的生成算法

定义八近邻图像的边界跟踪自动机,利用自动机跟踪图像所有区域边界,自动机的输出为边界的顶点链码,在自动机跟踪所有边界的同时生成围线的树结构。跟踪算法复杂度是线性的,能跟踪任意复杂图像区域。

有限布尔代数上的线性自动机

自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。

基于非确定树自动机的复合攻击建模研究

攻击模型是检测网络攻击的有效方法,通过对复合攻击建模方法的研究,提出一种基于非确定树形自动机的建模方法。该方法扩展和改进了传统攻击树的建模方法,基于非确定树自动机对复合攻击进行建模。自动机可以接受树形的数据结构的输入,复合攻击的攻击过程表现为树形自动机中从叶子节点到根节点的移动。该方法不但可以形式化描述复合攻击过程,并且能够检测正在发生的攻击和报告攻击完成水平。实验结果证实该方法的有效性。

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

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

一种嵌入式系统扩展流关系Petri网及应用

为了将数据流和控制流在同一个模型中明确标识,将经典Petri网的4元组结构扩展为7元组,定义一种新的嵌入式系统扩展流关系Petri网表示方法,应用该表示法对火车控制系统进行建模,并将该模转换成等价的时间自动机模型,用UPPAAL进行形式化验证。验证结果表明火车控制系统具有可达性和安全性,说明建立的模型是合理有效的。

基于决策树和DFA的老挝文敏感信息过滤算法

通过对老挝文语言特点的分析,提出一种基于确定有穷自动机和决策树的老挝文敏感信息过滤算法。将老挝文进行词汇划分和编码化处理,合理地解决老挝文与汉语书写上的差异性以及计算机读取存储出现乱码的问题;结合决策树的特点,构建老挝文敏感信息决策树,该树不依赖于词典,且可以实现实时更新;基于确定有穷自动机模型实现了老挝文敏感信息的检测和过滤,同时也实现了实时报警。实验表明,该过滤算法针对老挝文有较高的工作效率,同时也取得了较好的查全率和查准率。

一种基于状态事件故障树的软件安全性分析方法研究

目前,能够对航空航天、核电等领域中复杂嵌入式系统安全关键软件功能建模和故障分析的方法尚未得到统一;致使功能模型分析中缺乏安全属性来源,故障分析得到的危害无法在功能设计中得到避免.状态事件故障树是一种适合描述复杂系统中功能失效因果关系的建模技术,统一了功能建模和故障分析;但是,由于其缺乏精确语义,难以直接进行软件的安全性分析.为此,提出一种基于状态事件故障树的软件安全性分析方法:首先,通过元素映射以及逻辑门转换,将状态事件故障树扩展为附加故障语义信息的故障状态机;然后,将故障状态机转换到时间自动机;最后,在模型检测工具UPPAAL下进行安全性测试反例分析.本文使用燃气灶控制系统的实例进行分析.

基于静态分析的高精度程序日志解析技术

针对现有的程序日志解析技术准确率较低的问题,提出一种新的日志解析技术。该技术结合过程间和过程内程序分析,在程序的抽象语法树上进行过程间的方法调用分析,同时利用Java字符串分析技术进行过程内的数据流分析,将两者结合为程序源代码中的日志点构造自动机,并以自动机来匹配程序日志。实验结果表明,与现有的日志解析技术相比,该方法能够明显提高日志解析的精度。

面向维吾尔文的敏感信息过滤方法研究

在这个信息量爆炸性增长的时代,网络不良信息充斥在日常生活当中。为了构建洁净的网络环境,实现对网络维吾尔文中敏感信息的检测与过滤,通过分析维吾尔文的特点,将维吾尔文进行词干提取和编码化处理,再结合DFA和决策树提出了针对维吾尔文敏感信息过滤的相应方法。维吾尔文经过词干提取、编码化处理解决了维吾尔文书写顺序和形式多样、存储易出现乱码等问题。再结合决策树的特点,将转码后的维吾尔文信息存储于决策树节点上,将决策树的子节点按照特定编码进行顺序排列。这样维吾尔文文本信息进行敏感信息过滤时可以缩小检测范围,提高算法效率。

基于网络文本信息的敏感信息过滤算法

为实现对网络敏感信息的检测和过滤,提出一种基于确定有穷自动机的改进算法ST-DFA(swift tree DFA)。对传统的DFA过滤算法进行改进,不再依赖敏感信息语料库,只须建立一次敏感信息决策树,即可实现对网络信息的多次过滤;当敏感词语料库发生更新时,可以实现对敏感词的决策树的实时更新。实验结果表明,ST-DFA算法有较高的工作效率,适合当下对互联网敏感信息的检测与过滤。

基于微核结构的可二次开发语音平台

随着电子商务、客户服务等信息服务的普遍化,为了满足各种商业以及服务系统的需求,语音服务作为电信领域备受关注的一个热点,其应用领域也越来越广泛。本语音平台是基于语音技术,整合了网络资源,使用VoiceXML描述和控制语音逻辑的一种交互式服务系统。其特点是信息获取快速准确,以及客户服务多样化越来越明显。可广泛应用于证券电话委托、电话银行、信息查询、语音信箱、自动传呼系统、多功能小型用户交换机等领域。