有限自动机的积可逆性讨论

主要讨论了有限自动机运算后的可逆情况,给出了有限自动机串、并联后为可逆(弱可逆,延迟有限步(弱)可逆)的若干条件,最后对有限自动机的化合运算的可逆性进行了特别讨论．     

弱可逆有限自动机分解的一个结果

研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径。从输出权的角度讨论了一般的延迟r步弱可逆有限自动机M的分解问题,得到了它可以分解出k0（k0≤r）阶延迟元的一个充要条件,即M可以分解成延迟r-k0步弱可逆有限自动机和k0阶延迟元当且仅当M的所有状态的长k0输出权为1。     

拟（h，k）阶存贮线性有限自动机的一些结果

利用拟（r,r）阶存贮线性有限自动机可以轻松地构造出一个延迟r步弱可逆的有限自动机,这比文献[2]中通过Ra,Rb变换,对（r,r）阶存贮线性有限自动机进行一系列复杂烦琐的变换来构造一个延迟r步弱可逆的有限自动机的方法要简单可行。文章利用拟（r,r）阶存贮线性有限自动机,给出了一种构造延迟r步前馈可逆的线性有限自动机M和延迟r步前馈逆线性有限自动机时的简便方法。     

基于细胞自动机的公钥密码体制研究

为了解决高速实时信息传输的瓶颈问题,该文提出了一种基于细胞自动机理论的公钥密码算法.该算法以n个一维可逆细胞自动机为私钥,由它们构造出的二维Moore型不可逆的细胞自动机为公钥组成公钥密码体制.该算法实现简单,易于VLSI(超大规模集成电路)实现,有效地解决了复杂密码算法在高速实时信息传输时带来的瓶颈现象.     

线性有限自动机零状态的作用

通过零状态研究了线性有限自动机的一些性质,得到了线性有限自动机弱可逆的一些结果,并给出了最小线性子有限自动机的描述,最后给出了算法实现。     

机器人路径规划的元胞自动机算法

采用Moore型邻居规则建立机器人路径规划的元胞自动机模型和演化规则，通过对移动机器人的路径进行演化，讨论了周围环境已知情况下的移动机器人元胞自动机路径规划问题。在演化规则中增加危险度检测，使得机器人能够避免碰撞和穿越障碍，仿真实验结果表明，利用元胞自动机可以实现复杂环境的机器人路径搜索，避免死锁和碰撞，达到快速的最优路径。     

概率有限自动机积的覆盖性

提出了概率有限自动机的覆盖的定义,然后利用代数的方法讨论了概率有限自动机的全直积(限制直积)、级联积、圈积、并积的覆盖关系,证明了2个概率有限自动机的级联积(限制直积)覆盖它们的圈积(全直积),概率有限自动机的圈积的全直积覆盖它们的全直积的圈积,给出了概率有限自动机的弱同态与覆盖的关系,研究了概率有限自动机的积的覆盖关系的传递性质.     

基于元胞自动机的行人流疏散模拟研究

根据二维元胞自动机的Moore邻居确定行人运动规则,建立基于元胞自动机的行人流疏散模型,对房间内人员疏散过程进行模拟研究,得到了疏散时间与房间出口宽度、人员密度之间的变化关系.该模拟结果对紧急情况下的人员疏散具有一定的指导意义.     

有限自动机化合的一些结果

主要讨论了有限自动机的化合与化合前两个有限自动机的弱可逆性,严格延迟步数,弱逆以及线性的一些关系．     

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

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

一种非确定型有穷自动机的极小化方法

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言．确定型有穷状态自动机（DFA）极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机．而非确定型有穷状态自动机（NFA）极小化问题尚未找到有效算法．尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加．从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机．     

自适应元胞遗传算法与股票价格行为分析

与以往侧重于刻画从众模仿行为的元胞自动机价格模型不同,论文基于Moore型邻居投资者分布结构,以预测精度为切入点,将遗传算法引入到元胞自动机股票价格模型中,投资者与“邻居”沟通和分享信息,并由遗传算子来优化其对股价进行预测的各要素权重;研究了两种预测模式下的权重演化行为。以及权重交叉概率对股价行为（收敛性、波动性等）的影响;模拟了预期驱动下,股价与市场情绪的关系．研究认为：元胞遗传算法的引入,较好地驱动着股票价格回归基本价值,减轻了股票市场的波动性．     

Von Neumann正则环上的零因子图

讨论了一般Von Neumann正则环上的零因子图结构,重点刻画了其连通性和顶点性质.若R是有单位元的正则环,则其零因子图Γ(R)连通当且仅当R是直有限的;若R是无单位元的正则环,则其零因子图Γ(R)连通当且仅当R无真的单边恒等元;若R是满足|R|≥ 5的正则环,则其零因子图Γ(R)的源点和收点可以刻画为Sour(R)={a∈R|a是右可逆的但左不可逆},Sink(R)={a∈R|a是左可逆的但右不可逆}.     

关于概率自动机的等价性与极小化问题

本文给出了两概率自动机按顺序初始等价的充要条件,证明了初始等价的概率自动机的基矩阵秩必相等及判定极限极小概率自动机的一个充要条件.同时也更正了[1]中的一个错误。     

有限自动机的变换半群和它识别的信息

在离散时序系统的分析和控制中,要想知道这个系统的性质,即知道对这个系统提供什么信息(输入)才能使它达到所期望的状态或产生所需要的输出,这个问题涉及到有限自动机的识别问题。本文提出了使用(0,1)—矩阵去计算有限自动机的变换半群和它识别的信息,并且分析了各种特殊(0,1)—矩阵所代表的信息。     

基于蚁群算法的细胞自动机优化及其在电路测试中的应用

细胞自动机在电路设计、计算机安全等领域有广泛的应用.首先通过使用蚁群算法实现对细胞自动机结构的优化配置,从而产生具有较强随机性的伪随机数序列;其次,把细胞自动机应用于数字电路的测试,利用经优化后的二维细胞自动机来生成测试矢量.实验结果表明,经过蚁群算法优化之后得到的细胞自动机能够产生随机性较强的伪随机数序列,在数字电路测试的应用中能够提高故障覆盖率.     

Efficient Translation of LTL to Büchi Automata

The construction of Büchi automata from linear temporal logic is a significant step in model check-ing. This paper presents a depth-first construction algorithm to obtain simple Büchi automata from linear-time temporal logic which significantly reduces the sizes of the state spaces. A form-filling algorithm was used to reduce the size of the generated automata and the algorithms were applied directly to state-based Büchi automata, without transformation into transition-based automata. A form-filling algorit...