格值交替树自动机

交替（树）自动机因其本身关于取补运算的简洁性及其与非确定型（树）自动机的等价性,成为自动机与模型检测领域研究的一个新方向.在格值交替自动机与经典交替树自动机概念的基础上,引入格值交替树自动机的概念,并研究了格值交替树自动机的代数封闭性和表达能力.首先,证明了对格值交替树自动机的转移函数取对偶运算,终止权重取补之后所得自动机与原自动机接受语言互补这一结论.其次,证明了格值交替树自动机关于交、并运算的封闭性.最后,讨论了格值交替树自动机和格值树自动机、格值非确定型自动机的表达能力;证明了格值交替树自动机与格值树自动机的等价性,并给出了二者相互转化的算法及其复杂度分析;同时,提供了用格值非确定型自动机来模拟格值交替树自动机的方法.     

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。     

一类格值自动机的极小化

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

格值有限状态自动机的半群

提出了格值有限状态自动机的定义,给出了格值有限状态自动机的两种同余关系,研究了格值有限状态自动机的半群的若干性质,最后给出了两种有限半群E(A)和E(A)的关系。     

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

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

格值有限状态机子机的构造算法

给出了格值有限状态机（简记为LFSM）状态后继的概念,研究了它的性质,并提出了格值子机、格值真子机和基于格值子机的可分离性的概念,讨论了格值子机的若干性质。最后,给出了两个构造格值子机的算法,并通过实例验证了此算法。     

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

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

格值有限状态机的一些性质

讨论格值有限状态机强连通性、循环性、完全性以及交换性等一些代数性质,证明若两个格值有限状态机之间存在满足一定条件的同态映射时,它们之间的这些性质之间的关系,还给出了格值有限状态机的一些积的定义,以及对积的一些性质进行了讨论,也得到了一些结果。     

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

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

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

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

容差近似空间的广义概念格模型研究

在粗糙集合理论中,近似空间概念格之间存在着有趣的对应关系,利用概念格研究知识的约简和发现。更直观和更有效,但已有的概念格模型是基于近似空间的等价类划分的。等价类划分过于苛刻,扩展的基于容差关系的近似空间具有更广泛的意义,但目前未见有相应的格模型被提出。该文提出了容差近似空间的一种格模型,称为广义概念格,给出了定义,描述了建立方法和由它产生规则的原则,讨论了空间复杂性问题,并且与其它相近方法做了比较     

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

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

Automata theory based on complete residuated lattice-valued logic

This paper establishes a fundamental framework of automata theory based on complete residuated lattice-valued logic. First it deals with how to extend the transition relation of states and par-ticularly presents a characterization of residuated lattice by fuzzy automata (called (?) valued automata). After that fuzzy subautomata (called (?) valued subautomata), successor and source operators are pro-posed and their basic properties as well as the equivalent relation among them are discussed, from which it follows that the two fuzzy operators are exactly fuzzy closure operators. Finally an L bifuzzy topological characterization of Q valued automata is presented, so a more generalized fuzzy automata theory is built.     

Finite automata theory with membership values in lattices

In this paper, we study finite automata with membership values in a lattice, which are called lattice-valued finite automata. The extended subset construction of lattice-valued finite automata is introduced, then the equivalences between lattice-valued finite automata, lattice-valued deterministic finite automata and lattice-valued finite automata with ε-moves are proved. A simple characterization of lattice-valued languages recognized by lattice-valued finite automata is given, then it is proved that the Kleene theorem holds in the frame of lattice-setting. A minimization algorithm of lattice-valued deterministic finite automata is presented. In particular, the role of the distributive law for the truth valued domain of finite automata is analyzed: the distributive law is not necessary to many constructions of lattice-valued finite automata, but it indeed provides some convenience in simply processing lattice-valued finite automata.     

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.     

可换双剩余格上的广义模糊粗糙集及其公理化

双剩余格是t-模、t-余模、模糊剩余蕴涵及其对偶算子的代数抽象,基于格的L-模糊关系是普通模糊关系的推广。作为Pawlak经典粗糙集及多种模糊粗糙集模型的共同推广,提出了一种基于可换双剩余格及L-模糊关系的广义模糊粗糙集模型,引入了正则可换双剩余格的概念,并给出了基于正则可换双剩余格的广义模糊粗糙上、下近似算子的公理系统,推广了多个文献中已有的结果。     

RaRb Transformation of Compound Finite Automata over Commutative Rings

Some results on RaRb transformation of compound finite automata over finite field are generalized to the case of commutative rings.Properties of RaRb transformation are discussed and applied to the inversion problem for compound finite automata.     

确定型格值有限自动机的最小化

给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFA M=Q,Σ,δ,q₀,σ的实质是求取Q/R_k。由此以可到达状态为基础引入了等价关系R_k、S_k与商集Q/S_k,证明了R_k=R_k-1∩S_k,由此得到Q/R_k的等价类为Q/R_k-1中等价类与Q/S_k中等价类的非空交集全体。引入了H_k,并证明了可由H_k求取Q/S_k,从而得到仅利用集合运算便可求取Q/R_k的算法,最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。     

From quantitative to qualitative orness for lattice OWA operators

This paper deals with OWA (ordered weighted average) operators defined on an arbitrary finite lattice endowed with a t-norm and a t-conorm. A qualitative orness measure for any OWA operator is suggested, based on its proximity to the OR operator that yields the maximum of the given data. In the particular case of a finite distributive lattice, considering the t-norm given by the meet and the t-conorm given by the join, this qualitative measure agrees with the value that some discrete Sugeno integral takes on the vector consisting of all the members of the lattice. Some applications of the qualitative orness of OWA operators to decision-making problems are shown. In addition, OWA operators defined on a finite product lattice are also applied in image processing. We analyze the effect of several OWA operators with respect to their orness.