非确定有穷自动机在盲文转码中的应用

对盲人使用的计算机交互技术进行研究是很有意义的工作。盲文字库缺少国际标准和不同公司的盲文字库不兼容造成了很多难题。将盲文用汉字点位编码表示,能摆脱盲文字库的束缚。用不确定有穷自动机描述盲文与汉字点位编码的转换过程,再用逆序拆分子集法对其确定化。经测试系统的转码正确率达到100%,从而实现盲文与机器无关,使得盲人使用计算机更方便。     

PSL构造双向交换自动机及非确定自动机的方法

PSL(property specification language)是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL(foundation language)和分支时序逻辑OBE(optional branching extension)两部分.由于OBE就是CTL(computation tree logic),并且具有时钟声明的公式很容易改写成非时钟公式,因此重点研究了非时钟FL逻辑.为便于进行模型检验,每个FL公式必须转化成为一种可验证形式,通常是自动机(非确定自动机).构造非确定自动机的过程主要是通过中间构建交换自动机来实现.详细给出了由非时钟FL构造双向交换自动机的构造规则.构造规则的核心逻辑不仅仅局限于是在LTL(linear temporal logic)基础上的正规表达式,而且全面而充分地考虑了各种FL操作算子的可能性.并且给出了将双向交换自动机转化为非确定自动机的一种方法.最后,编写了将PSL转化为上述自动机的实现工具.FL双向交换自动机的构造规则计算复杂度仅是FL公式长度的线性表达式,验证了构造规则的正确性.在此基础上,证明了双向交换自动机与其转化的等价的非确定自动机接受的语言相同.上述工作对解决复杂并行系统建模和模型验证问题具有重要的理论意义和应用价值.     

基于不确定有限自动机的蒙古文校对算法

该文首先分析了蒙古文电子文本中存在的错误类型、出错原因以及常用的查错纠错方法,然后根据蒙古文特有的书写习惯和编码特点提出一种基于不确定有限自动机的校对算法。该算法采用有限自动机的方法对校对算法所依据的知识词典进行描述,大大提高了文本查错和纠错速度。     

基于多耦合元胞自动机的加密算法

提出了耦合系数的概念,构造了一个新的耦合元胞自动机模型,并分析了耦合系数对耦合元胞自动机时空演化的影响。针对已有的单耦合元胞自动机加密系统中存在的不足,提出了基于多耦合元胞自动机的加密算法,该算法将多个元胞进行耦合,增强了两个元胞自动机之间的作用,扩大了相互影响的范围,使得误差扩散更为快速。仿真结果表明,该算法具有更为理想的扩散和扰乱特性,可抵抗蛮力攻击和差分分析攻击。     

元胞自动机可逆性研究

元胞自动机是对复杂适应系统建模的重要理论工具。可逆性是元胞自动机的一个重要属性,是模拟物理可逆空间的必要条件。本文介绍元胞自动机的基本概念、可逆性和可计算性,并介绍一维可逆元胞自动机可计算的证明思路。     

细胞自动机反向迭代加密技术研究

细胞自动机固有的组成单元的简单性、单元之间作用的局部性和信息处理的高度并行性 ,并表现出复杂的全局特性等特点使得细胞自动机尤其适合于密码学中的应用 .该文简述了细胞自动机的基本概念 ,研究了基于细胞自动机反向迭代的输出序列熵最大化加密技术 ,并对系统保密性进行了分析 .     

基于元胞自动机模型的礼堂人群疏散仿真

为了消除礼堂的安全隐患,制定行之有效的应急预案,有必要对礼堂人群疏散运动进行研究,掌握礼堂人群疏散的一般特点和规律。采用基于二维元胞自动机模型对某高校礼堂发生人群疏散运动进行仿真,找出影响礼堂人群疏散效率的关键因素,为高校礼堂设计提供支持;为高校礼堂制定突发事件应急预案提供参考。     

Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata

We show that the problem of checking careful synchronizability of partial finite automata is PSPACE-complete. Also the problems of checking D ₁-, D ₂-, and D ₃-directability of nondeterministic finite automata are PSPACE-complete; moreover, the restrictions of all these problems to automata with two input letters remain PSPACE-complete.     

基于细胞自动机的动态多秘密共享方案

针对现有基于细胞自动机多秘密共享方案存在安全性较低和可扩展性较差的问题,提出了一种可验证的动态门限多秘密共享方案.方案中参与者的子秘密可以在多次秘密共享过程中重复使用,减少了秘密分发者的计算负担;在不改变现有参与者子秘密的前提下,可动态加入新参与者和新共享秘密;在秘密分发和重构过程中,能够实现参与者对秘密分发者以及秘密重构者对参与者的验证,及时检测和识别分发者对参与者以及参与者对重构者的欺骗,提高了重构秘密的成功率以及方案的安全性.     

基于Matlab的元胞自动机的仿真设计

元胞自动机不仅是理论计算机科学领域的一个重要的计算模型 ,而且可视为一无限维的离散动力系统 ,被广泛应用于自然科学和社会科学各领域的复杂性的研究中 ,是一个重要的研究方法和工具。该文以Matlab为开发工具 ,开发了元胞自动机的可视模型 ,为其在各个领域的复杂性研究提供了一个简易、可行的计算机仿真工具。     

基于细胞自动机的安全图像加密算法

利用初等细胞自动机状态环性质进行加密后的密文图像仍可看出原图像的部分轮廓,且明文敏感性差。由此提出一种安全的图像加密算法,采用周期为2的二维细胞自动机对图像进行位平面加密,再通过状态环加密的方法使明文改变1 bit即可影响整个密文图像。仿真结果表明,改进算法敏感性更高,密钥空间更大,且加密速度较快。     

一种基于元胞自动机的图像拼接方法

描述了一种基于元胞自动机的图像拼接方法,采用元胞自动机提取图像特征点,然后以特征点邻域灰度互相关法进行特征点匹配,最后根据匹配的特征点对得到图像间的变换参数。实验结果表明,本方法不仅准确实现了图像拼接,而且降低了图像重叠度的要求。     

Non-uniform Cellular Automata based on Open-ended Rule Evolution

Cellular automata (CAs) are mathematical models of spatially and temporally discrete mathematical systems. Non-uniform CAs are the cellular automata in which each cell may contain a different transition rule and change it with time, while all cells share the same transition rule in regular CAs. Little is still known about the dynamics of open-ended evolution of rules in non-uniform CAs. The purpose of our study is to construct and investigate a model of non-uniform CAs capable of open-ended rule evolution exhibiting a wide variety of behavior across all Wolfram’s classes. For this purpose, we construct 1-dimensional 2-state 3 neighborhood non-uniform CAs with evolving transition rules. In the model, we found an interesting dynamics that Class II (periodical behavior) and III (chaotic behavior) patterns emerged alternately, between which Class IV patterns sometimes emerged.     

细胞自动机函数优化算法

细胞自动机广泛用于仿真、建模，提出用细胞自动机进行函数优化。该思想与演化算子结合的算法CAMGA在试验中取得了很好的效果。其中对BUMP问题的求解优于现今已经发表的结果。     

基于PageRank算法改进的元胞自动机模型

针对在线零售业务系统中用户要进入许多无关页面才能找到所需商品的问题,站点应能根据群体用户购买兴趣动态调整网页分配,即站点自适应。借用PageRank算法对元胞自动机模型进行改进,实现站点的自适应调整。与原模型相比,改进模型的演化规则简单、时间复杂度低、性能更优越。     

细胞自动机置换群加密技术研究

1.引言信息技术的发展对信息安全提出了更高的要求,并使得作为信息安全核心的加密技术及其实现变得越来越复杂。所以,人们开始探索简化加密系统实现的新方法,以满足现代信息技术发展对全方位多层次信息安全的要求。1948年,Von Neumann在研究具有自组织特性的系统时引入了细胞自动机的概念,后经S.Wolfram对其结构进行简化,从而极大地推动了细胞自动机理论及其应用的发展。细胞自动机具有组成单元的简单性、单元之间作用的局部性和信息处理的高度     

基于元胞自动机的线性遗传程序设计算法

为维持进化过程中的种群多样性,并进一步提高求解问题的精确度,在SGP算法的基础上引入元胞自动机模型理论,提出一种能够实现具有细粒度并行的CSGP算法.该算法可提高求解问题的成功率以及减少进化代数,对比实验表明,CSGP算法较GEP算法和SGP算法在求解符号回归的问题上有较好的性能优势.     

一类基于元胞自动机的传染病模型的仿真

研究传染病优化控制建模,为了解决早期监测预警体系,考虑到传染病不能统一处理的各种影响因素,针对未能很好的体现疾病传播过程中人的行为特征的影响,从病毒在群体内传播行为的多样性特点出发,借助于网络病毒生长过程及拓扑结构,提出构造新的元胞自动机模型,对病毒在人群接触网络内的传播过程进行了仿真,并在此基础上研究了疫苗注射比率、病毒变异频率、个体反应时间对病毒传播的影响,同时针对病毒的传播特点提出了有效的防治策略.以甲型HIN1为实例,实验结果表明,元胞自动机模型能较好地仿真病毒的传播过程,在疾病预防和控制方面有较高的应用价值.