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

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

确定型模糊多重集有限自动机的极小化

主要研究确定型模糊多重集有限自动机的状态极小化问题。给出了模糊多重集有限自动机的同余和同态概念,并利用同余和同态关系研究了确定型模糊多重集有限自动机的极小化问题。进一步从确定型模糊多重集有限自动机自身出发,构造出极小模糊多重集有限自动机,并给出了极小化的算法。     

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

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

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

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

两类具有输出字符功能的模糊自动机的关系

在文中,对文献8中介绍的具有输出字符功能的模糊自动机和模糊有限状态自动机的定义作了修改,并对它们进行了系统的研究,揭示了此两类自动机和取分配格的代数性质的紧密联系;得到了此两类自动机在:(1)强等价;(2)等价;(3)弱等价条件下的许多重要结论。     

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

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

模糊树自动机语言的封闭性

给出了[Σ-]代数、[Σ-]树、模糊[Σ-]树自动机、模糊[Σ-]树自动机行为的定义。引入了模糊树自动机语言的并、交、连接和Kleene闭包运算,证明了在这些运算下模糊树自动机语言的封闭性。     

扰动值模糊有限自动机及其语言*

引入扰动值模糊有限自动机及其语言的概念,讨论扰动值模糊有限自动机的状态转移函数的扩张问题,证明3类确定型扰动值模糊有限自动机、非确定型扰动值模糊有限自动机相互等价性,研究扰动值模糊有限自动机的语言关于正则运算的封闭性.     

一种模糊自动机的新模型

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

一种模糊自动机的新模型

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

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata are discussed. The notions of intuitionistic fuzzy recognizer, complete accessible intuitionistic fuzzy recognizer, intuitionistic fuzzy finite automata, deterministic intuitionistic fuzzy finite automata, and intuitionistic fuzzy language are introduced. It is shown that the languages recognized by intuitionistic fuzzy recognizer are regular, and the intuitionistic fuzzy languages recognized by the intuitionistic fuzzy finite automaton and the intuitionistic fuzzy languages recognized by deterministic intuitionistic fuzzy finite automaton are equivalent. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program(Grant No.2002CB312200).     

Determinization of fuzzy automata with membership values in complete residuated lattices

In this paper we introduce a new method for determinization of fuzzy finite automata with membership values in complete residuated lattices. In comparison with the previous methods, developed by Bělohlávek [R. Bělohlávek, Determinism and fuzzy automata, Information Sciences 143 (2002), 205-209] and Li and Pedrycz [Y.M. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets and Systems 156 (2005), 68-92], our method always gives a smaller automaton, and in some cases, when the previous methods result in infinite automata, our method can result in a finite one. We also show that determinization of fuzzy automata is closely related to fuzzy right congruences on a free monoid and fuzzy automata associated with them, and in particular, to the concept of the Nerode’s fuzzy right congruence of a fuzzy automaton, which we introduce and study here.     

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

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

The relationships among several types of fuzzy automata

We discuss the relationships among several types of fuzzy automata in which all fuzzy sets are defined by membership functions whose codomains are a lattice-ordered monoid L. These automata include nondeterministic L-valued finite automata with Λ-move, nondeterministic L-valued finite automata, deterministic L-valued finite automata, and L-valued finite-state automata. We consider all that come with fuzzy initial states and fuzzy final states or with crisp initial states or crisp final states. Some comparative results concerning the power of fuzzy automata used in the existing literature to recognize fuzzy languages are given systematically.     

Formal power series and regular operations on fuzzy languages

In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series.     

An improved algorithm for determinization of weighted and fuzzy automata

For a given weighted finite automaton over a strong bimonoid we construct its reduced Nerode automaton, which is crisp-deterministic and equivalent to the original weighted automaton with respect to the initial algebra semantics. We show that the reduced Nerode automaton is even smaller than the Nerode automaton, which was previously used in determinization related to this semantics. We determine necessary and sufficient conditions under which the reduced Nerode automaton is finite and provide an efficient algorithm which computes the reduced Nerode automaton whenever it is finite. In determinization of weighted finite automata over semirings and fuzzy finite automata over lattice-ordered monoids this algorithm gives smaller crisp-deterministic automata than any other known determinization algorithm.     

A fuzzy automaton synthesis method

A fuzzy automaton is defined and some function properties in the fuzzy logic, in particular the existence theorem of those functions, are recalled. A synthesis method is then proposed. It consists of determining the state vector dimension, the evolution functions and the observation functions of the fuzzy automaton. An example is given to illustrate the efficiency of this method.     

一类格值自动机的极小化

给出了格值自动机的同余和同态,从代数角度出发详细研究了同余和同态关系的代数性质,揭示了格值自动机的代数性质和取值格半群的紧密联系,利用同余和同态关系最终研究了格值自动机的极小化问题,在正则同余下给出了可在有限步实现具有模糊初始状态和特殊模糊终状态的自动机极小化的算法。