利用等价类构造有限状态自动机

一类语言由任意字母表上的某种进制的数字串构成，要求该语言中的所有数字串能够整除N；构造有限状态自动机识别该类语言是困难的，本文提出了根据等价类构造一类有限状态自动机的方法。该方法可以针对所有字母表和所有进制的数字串构成的语言，而且满足语言中的所有数字串能够整除任意正整数N。该方法实用、简便。     

模糊有限自动机的最小化算法优化

现有的模糊自动机最小化算法没有涉及到对模糊自动机状态的隶属度迁移和变化的讨论,优化的模糊自动机最小化算法弥补了这类算法的不足之处。该算法将模糊有限自动机首先转化为单个初始状态的模糊自动机,然后再将转化后的模糊自动机化简为最小模糊自动机,算法在转化过程中单独讨论了模糊自动机状态隶属度的转化方式,使得算法更加严谨和简化。     

循环自动机的等价性

主要讨论了两个循环有限自动机的等价性与循环有限自动机的生成子之间的关系,在某些条件下给出了两个循环有限自动机等价的充分必要条件。     

下推自动机的状态转换图与下推自动机的化简

参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。     

格值有限自动机等价判定算法

引入了完备L-Fuzzy矩阵的概念,给出了基于格半群的模糊有限自动机的形式化定义,即完备格值有限自动机,研究了它的主要性质;给出了完备格值有限自动机的行为矩阵,从行为矩阵出发,给出了自动机状态等价和自动机等价的定义。最后,得到了该类自动机等价的判定算法。     

带空移动的加权有限自动机量化等价及其转换

在经典的有限自动机理论中,带空移动的有限自动机与不带空移动的有限自动机是等价的。取值于实数的加权有限自动机是自动机的一种推广模型,它给经典自动机的每个转换赋一个取值于实数的权值,这些权值表示执行转换的代价。为了研究带空移动的加权有限自动机与不带空移动的加权有限自动机是否具有等价性这一问题,提出量化等价的概念,并研究如何将一个带空移动的加权有限自动机转换为一个与之量化等价的不带空移动的加权有限自动机。研究结果表明:这两者是量化等价的。     

格值有限状态自动机的同态和商自动机

提出了格值有限状态自动机（LFSA）的同态、强同态的概念,研究了LFSAs同态、强同态的若干性质。在LFSAs强同态的基础上,得到了LFSA的商自动机及其最小化自动机,刻画了商自动机的性质。     

基于有限状态自动机的服务组合模型

分析了目前服务计算的研究现状和存在的问题，在D Berardi和A Wombacher的基础上提出了一种带条件的有限状态自动机模型cFSA（Finite State Automata with condition），并给出了基于cFSA的服务理论模型．在该服务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型，并给出了该模型的代数性质和实现方法．     

一种模糊自动机的新模型

通过对秃头悖论的讨论分析,对传统自动机模式是否适用于模糊自动机进行分析论证,指出传统自动机模型的缺陷在于没有模糊性,不能处理模糊的事物,并对模糊自动机的旧模型提出质疑,因为旧模型固定的隶属度无法表达模糊事物的变化过程,最后从量变和质变角度提出一种模糊自动机的新模型。     

一种模糊自动机的新模型

通过对秃头悖论的讨论分析,对传统自动机模式是否适用于模糊自动机进行分析论证,指出传统自动机模型的缺陷在于没有模糊性,不能处理模糊的事物,并对模糊自动机的旧模型提出质疑,因为旧模型固定的隶属度无法表达模糊事物的变化过程,最后从量变和质变角度提出一种模糊自动机的新模型。     

模糊有穷自动机与单体二阶Lukasiewicz逻辑

该文引入了单体二阶Lukasiewicz逻辑,进而给出了模糊有穷自动机识别语言的逻辑描述,证明了多值逻辑意义下的Bchi与Elgot基本定理.通过引入星-自由模糊语言与非周期模糊语言,刻画了可以用一阶Lukasiewicz逻辑定义的模糊语言.     

基于等价关系的有穷自动机最小化方法

主要介绍了有穷自动机的基础知识,研究了有穷自动机的等价性,并在确定型有穷自动机的状态集上引入等价关系,给出了自动机的最小化过程。利用等价归并算法,可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉．生成与其等价的最小化的确定型有穷自动机。     

基于等价关系的有穷自动机最小化方法

主要介绍了有穷自动机的基础知识,研究了有穷自动机的等价性,并在确定型有穷自动机的状态集上引入等价关系,给出了自动机的最小化过程。利用等价归并算法,可以将某一给定的确定型有穷自动机状态集上的等价状态归并掉,生成与其等价的最小化的确定型有穷自动机。     

Generalized Statistical Equivalence of Automata

The notion of generalized statistical equivalence of automata is introduced, and this equivalence is demonstrated to be weaker than the usual equivalence but stronger than the statistical equivalence of automata.     

矩阵模型表示下有限自动机等价判定方法

该文在有限自动机的矩阵模型表示方法1基础上,采用矩阵理论和布尔代数为工具,提出了一种有限自动机等价判定的新方法。该方法不仅有利于算法设计和计算机自动处理,其处理方法对采用矩阵模型研究有限自动机理论及应用问题也有一定学术参考价值。     

量子Mealy自动机和量子Moore自动机的等价

随着大数分解的量子算法和量子搜索算法的给出,量子计算进入了一个全新的迅速的发展时期.量子自动机是近十年来兴起的量子计算理论,是一个很活跃的研究领域,量子自动机的研究已经相当丰富.首先定义了字符集上的有限维Fock空间,给出基于有限维Fock空间的量子Mealy自动机和量子Moore自动机的定义,考虑在不受外界环境影响下的两种量子自动机构成的封闭的量子系统,详细地研究了量子Mealy自动机和量子Moore自动机的演化过程,利用量子力学中密度算子的基本理论给出量子Mealy自动机和量子Moore自动机生成的量子语言.最后,在考虑纯态的情形下证明了量子Mealy自动机与量子Moore自动机是等价的.     

同步格值自动机的约简和最小化算法

引入了完备L-Fuzzy矩阵的概念,提出了取值于格半群上的输入字符和输出字符长度相同的模糊自动机的概念,即完备的同步格值自动机的概念,研究了它的主要性质;从行为矩阵出发,给出了完备的同步格值自动机状态等价和自动机等价的定义,从自动机的状态等价,研究了该自动机可约简的条件,并得到了该自动机的最小化算法。     

Mizumoto格值有限自动机及其最小化

提出取值为格半群的Mizumoto格值有限自动机的概念,得到基于模糊字符串的Mizumoto格值有限自动机的扩张模型,并详细讨论了其性质。同时建立了扩张Mizumoto格值有限自动机与标准扩张Mizumoto格值有限自动机的等价性,在此基础上给出了其最小化算法。     

模糊识别器与有穷自动机的等价性

针对模糊识别器与有穷自动机的关系,证明了当输入字母表相同时,任给一个模糊识别器,必然存在一个有穷自动机,使得模糊识别器的行为与有穷自动机所接受的语言相同;反之,任给一个有穷自动机,必然存在一个模糊识别器,使得有穷自动机所接受的语言与模糊识别器的行为相同,从而得出它们之间的等价性。