有限模糊树自动机的一些代数性质与相应的语言

将模糊自动机的同态、完全、容许关系等概念引入到模糊树自动机中,从代数的角度研究模糊树自动机的一些代数性质,并探讨了模糊树自动机的语言的相关问题.     

可逆模糊自动机

首先提出了可逆模糊自动机的概念,研究了能被可逆模糊自动机接受的语言(简记为F(∑))的一些性质.其次给出了自由群上被可逆模糊自动机接受的模糊子集的概念,详细研究了可逆模糊语言与经典可逆语言的关系.最后,通过引入语法幺半群刻画了F(∑)的代数性质.通过这些性质可以有效的判断一个模糊语言是否能被一个可逆模糊自动机接受.     

模糊剩余自动机

在[0,1]格值区间上引入了模糊剩余自动机(FRFA)的概念:若一个模糊自动机(FFA)的每一个状态都定义了其接受语言的一个剩余语言,则称为模糊剩余自动机.讨论了模糊剩余自动机的一些性质以及模糊自动机的消去与饱和运算.在定义既约模糊剩余语言的基础上定义了标准模糊剩余自动机,并给出了构造方法.证明了一个模糊正则语言对应的标准FRFA即为识别这个语言的最小状态FFA,此研究为模糊自动机的状态最小化研究提供了另一种研究思路.     

两类循环模糊自动机的弱等价性

定义循环模糊自动机和循环模糊有限状态自动机,并讨论了这两类循环模糊自动机的弱等价性.     

模糊树自动机的同余与同态

从代数角度出发研究模糊树自动机的同余与同态,得出模糊树自动机的同态基本定理和同构基本定理,且对模糊树自动机的语言及模糊树自动机的极小化问题进行研究.     

幺半环上模糊有限状态自动机积的覆盖关系

提出了幺半环上模糊有限状态自动机的各种乘积以及覆盖的定义,并得到了一些性质.证明了直积、级联积、圈积三种乘积以及和之间的覆盖关系,得到了乘积自动机、和自动机覆盖关系的一些代数性质.     

通用模糊自动机

首先使用模糊语言的分解定义了通用模糊自动机:这个自动机以该模糊语言的分解作为状态,通过模糊语言的包含度定义其转移函数。其次定义了模糊自动机上的态射,证明了接受给定模糊语言的所有自动机都可以标准地映射到该语言对应的通用模糊自动机上,这个性质称为通用性。最后进一步讨论了模糊商自动机,模糊m-最小自动机,模糊最小自动机及与通用模糊自动机之间的关系。     

模糊Rabin自动机和模糊Game自动机的等价性

自动机是理论计算机的一个重要的研究内容.模糊Rabin自动机和模糊Game自动机是经典自动机的延续,给出了模糊Rabin自动机和模糊Game自动机的相关定义,讨论各自的内在性质,并得到了二者的等价关系.这进一步丰富了模糊自动机理论.     

模糊无限状态自动机及其收敛性

到目前为止,我们所研究的模糊或非模糊的自动机都是有限状态自动机.然而,关于无限状态自动机的定义及它的稳定性和收敛性都没有被讨论过.本文中,我们使用离散的反馈神经网络及网络输出空间划分方法,同时,在梯度更新算法中使用伪梯度方法,给出了模糊无限状态自动机收敛到模糊有限状态自动机的证明.     

最小化基于合成模糊变换的模糊自动机

经过重新定义模糊自动机,使得模糊自动机的识别过程与一个合成模糊变换(CF变换)一致,而且得到了尊重合成模糊变换的最粗分类即为状态集的最粗等价分类这一重要结论.在对尊重合成模糊变换的最粗分类的讨论中,给出了找到尊重合成模糊变换的最粗分类的有限步算法,亦即状态集的最粗等价分类和最小化模糊自动机的算法.该算法不仅给出了最长运算时间,而且还给出可终止算法的条件,使得运算更为可行和简便.     

Bisimulations for fuzzy automata

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata A and B is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on A and B and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata A and B are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of A and B with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.     

New directions in fuzzy automata

Automata are the prime example of general computational systems over discrete spaces. The incorporation of fuzzy logic into automata theory resulted in fuzzy auotomata which can handle continuous spaces. Moreover, they are able to model uncertainty which is inherent in many applications. Deterministic Finite-state Automata (DFA) have been the architecture, most used in many applications, but, the increasing interest in using fuzzy logic for many new areas necessitates that the formalism of fuzzy automata be more developed and better established to fulfill implementational requirements in a well-defined manner. This need is due to the fact that despite the long history of fuzzy automata and lots of research being done on that, there are still some issues which have not been well-established and issues which need some kind of revision. In particular, we focus on membership assignment, output mapping, multi-membership resolution, and the concept of acceptance for fuzzy automata. We develop a new general definition for fuzzy automata, and based on that, develop well-defined and application-driven methodologies to establish a better ground for fuzzy automata and pave the way for forthcoming applications.     

Fuzzy automata and life

Boolean cellular automata may be generalized to fuzzy automata in a consistent manner. Several fuzzy logics are used to create 1‐dimensional automata and also 2‐dimensional automata that generalize the game of life. These generalized automata are investigated and compared to their Boolean counterparts empirically and using rule entropy and repeated input response functions. Fuzzy automata offer new mechanisms for classification of classical automata and can be used for insight into their qualitative behavior. © 2002 Wiley Periodicals, Inc.     

Minimization algorithm of fuzzy finite automata

In this paper, a class of fuzzy finite automata corresponding to the Mealy type of ordinary automata is formulated, and also two types of statewise equivalence relations are introduced. From the equivalence relations, a minimal form is defined and a minimization algorithm of the Mealy type of fuzzy finite automata is obtained.     

Fuzzy automata based on lattice-ordered monoid with algebraic and topological aspects

The purpose of this work is to study some algebraic and topological concepts of fuzzy automata with the membership values in lattice-ordered monoids. Unlike the usual fuzzy automata, we show that such concepts are affected by the associated monoid structure.     

Lattice valued relations and automata

A lattice-valued relation, lvr for short, from a set X to a set Y is a function from the Cartesian product of X and Y to a lattice. This concept is a generalization of other structures, notably tolerance spaces, nets and automata, separately investigated by the authors elsewhere. It is adequate to admit a natural definition of homogeneity and a classification of homogeneous lvr's by their isomorphism groups. The main result of the present paper is a proof of this classification. The application of this to automata, also interpretable as lvr's, is described, and an example given. We conclude with a brief discussion of the lvr theory of fuzzy and stochastic automata.     

BL-general fuzzy automata and accept behavior

In this note, we focus on behavior of BL-general fuzzy automata (for simplicity BL-GFA) and we obtain the free realization for a given behavior, that is, a BL-general fuzzy automaton whose behavior is given behavior. Then we find the realization with the minimum number of states. The minimization takes two steps: at first discard all superfluous states, and then we merge all pairs of states which have the same behavior. Moreover we prove some theorems. In particular, we show that the minimal reduction of the reachable part of an BL-GFA is the minimal realization of the behavior it. Finally we give some examples to clarify these notions.     

Deterministic automata simulation, universality and minimality

Finite automata have been recently used as alternative, discrete models in theoretical physics, especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/ extrinsic perception (see, for instance [3, 6, 18–21]). These studies deal with Moore experiments; the main result states that it is impossible to determine the initial state of an automaton, and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For this aim the classical theory of finite automata — which considers automata with initial states — is not adequate, and a new approach is necessary. A study of finite deterministic automata without initial states is exactly the aim of this paper. We will define and investigate the complexity of various types of simulations between automata. Minimal automata will be constructed and proven to be unique up to an isomorphism. We will build our results on an extension of Myhill-Nerode technique; all constructions will make use of “automata responses” to simple experiments only, i.e., no information about the internal machinery will be considered available.     

Homology theories and tolerance automata

We present three possible approaches to a homology theory of automata. Two of these require the state to possess a tolerance. This permits us to proceed by analogy with either the simplicial or the cubical theories of the topological category. The third approach describes a homology theory of automata as such.Fixed simplex theorems are stated. It is suggested that homology theory might be used to classify automata.