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.     

具有输出字符功能的模糊自动机的最小化问题

通过文献[8]中两类具有输出字符功能的Fuzzy自动机和Fuzzy有限状态自动机的强等价性,等价性和弱等价性的条件,在以往仅仅给出的Fuzzy有限状态自动机的最小化问题基础上,讨论了具有更广泛意义的具有输出字符功能的Fuzzy自动机的最小化问题,以及其最小化自动机与Fuzzy有限状态自动机的最小化自动机在不同条件下的关系。     

A transfer algorithm for hierarchical clustering

Transfer algorithms are usually used to optimize an objective function that is defined on the set of partitions of a finite set X. In this paper we define an equivalence relation ? on the set of fuzzy equivalence relations on X and establish a bijection from the set of hierarchies on X to the set of equivalence classes with respect to ?. Thus, hierarchies can be identified with fuzzy equivalence relations and the transfer algorithm can be modified in order to optimize an objective function that is defined on the set of hierarchies on X.     

Neural fuzzy point processes

Synaptic events in neural systems were described as generated by an apparatus @ possessing memory and encoding a fuzzy point process (the presynaptic discharge) into another N (the postsynaptic discharge). @ was considered to be a fuzzy automata, for which state membership is dependent on input membership and distribution as well as on a control exercised by other neural structures. In such a device, irregular input distributions favour a direct monotonic codification, whereas regular ones induce discontinuous and inverse relations between both fuzzy point processes. Both behaviors favour analogic and membership relations between the fuzzy input and output. However, there exist intermediate grades of irregularities which result in a context-free encoding, where similitude and equivalence relations predominate. The importance of such findings to neurophysiology is discussed.     

Fuzzy partitions and relations; an axiomatic basis for clustering

In this paper some connections between fuzzy partitions and similarity relations are explored. A new definition of transitivity for fuzzy relations yields a relation-theoretic characterization of the class of all psuedo-metrics on a fixed (finite) data set into the closed unit interval. This notion of transitivity also links the triangle inequality to convex decompositions of fuzzy similarity relations in a manner which may generate new techniques for fuzzy clustering. Finally, we show that every fuzzy c-partition of a finite data set induces a psuedo-metric of the type described above on the data.     

幺半环上几类模糊自动机的关系

给出了幺半环上非确定的模糊自动机和确定的模糊自动机及其语言的定义,证明了幺半环上三类非确定的模糊自动机间的等价性和三类确定的模糊自动机间的等价性,讨论了幺半环上三类非确定的模糊自动机和第四类非确定的模糊自动机之间的关系,以及幺半环上非确定的模糊自动机和确定的模糊自动机之间的关系.     

Finite-valued indistinguishability operators

Fuzzy equality relations or indistinguishability operators generalize the concepts of crisp equality and equivalence relations in fuzzy systems where inaccuracy and uncertainty is dealt with. They generate fuzzy granularity and are an essential tool in Computing with Words (CWW). Traditionally, the degree of similarity between two objects is a number between 0 and 1, but in many occasions this assignment cannot be done in such a precise way and the use of indistinguishability operators valued on a finite set of linguistic labels such as small, very much, etc. would be advisable. Recent advances in the study of finite-valued t-norms allow us to combine this kind of linguistic labels and makes the development of a theory of finite-valued indistinguishability operators and their application to real problems possible.     

Homological equivalence relations on an algebraic curve

We study the collection of homological equivalence relations on a fixed curve. We construct a moduli space for pairs consisting of a curve of genus g and a homological equivalence relation of degree n on the curve, and a classifying set for homological equivalence relations of degree n on a fixed curve, modulo automorphisms of the curve. We identify a special type of homological equivalence relations, and we characterize the special homological equivalence relations in terms of the existence of elliptic curves in the Jacobian of the curve.     

Suborbits and group extensions of flows

Given a pair of an ergodic measured discrete equivalence relationR and a subrelationS ⊂R of finite index, a classification of the inclusion up to orbit equivalence will be discussed. In case of amenable and type III₀ relations, the orbit equivalence classes of inclusions will be completely classified in terms of a collection of a subgroupH and a normal subgroupG ₀ of a finite groupG and an ergodic group (G/G ₀) extension of a nonsingular flow. This is a generalization of Krieger’s theorem by which orbit equivalence classes of single relations were classified. Due to this result, essential type III inclusions will be made clear. Supported by the Japan Ministry of Education, Grant-in-Aid for Scientific Research No. (C)07640223. An erratum to this article is available at .     

Equivalence and traces on C1-algebras

We introduce an equivalence relation among the positive elements in a C¹ and show that the algebra is (semi-) finite if and only if there is a separating family of (semi-) finite traces. Concentrating on simple, semi-finite C¹-algebras we relate geometrical properties in the cone of equivalence classes to functional analytic properties of the algebra, such as the number of normalized traces and their possible values on a given element. The paper may be considered as an attempt to extend Murray and von Neumann's type and equivalence theory to C¹-algebras.     

Equivalence of operations with respect to discriminator clones

For each clone C on a set A there is an associated equivalence relation, called C-equivalence, on the set of all operations on A, which relates two operations iff each one is a substitution instance of the other using operations from C. In this paper we prove that if C is a discriminator clone on a finite set, then there are only finitely many C-equivalence classes. Moreover, we show that the smallest discriminator clone is minimal with respect to this finiteness property. For discriminator clones of Boolean functions we explicitly describe the associated equivalence relations.     

Eigen fuzzy sets and fuzzy relations

When R is a fuzzy relation between the elements of a finite set X, the fuzzy sets A of X such that R ° A = A (MAX-MIN composition) are called eigen fuzzy sets. The main result of this paper is the determination of the greatest eigen fuzzy set associated with a given fuzzy relation and we give three methods illustrated by an example. We then state that the greatest eigen fuzzy set associated with $\text{R}\text{?}$, the transitive closure of R, is exactly the one associated with R. Finally we describe how to obtain all fuzzy relations keeping invariant a given fuzzy set.     

Rouquier blocks in Chevalley groups of type E

In finite Chevalley groups of type E, we shall find a ‘Rouquier’ like block algebra in non-defining characteristic. We construct a Morita equivalence between this block and a principal block of a local subgroup. As an application of the equivalence, we shall determine some decomposition numbers in type E.     

Twisted affine Lie superalgebra of type Q and quantization of its enveloping superalgebra

We introduce a new quantum group which is a quantization of the enveloping superalgebra of a twisted affine Lie superalgebra of type Q. We study generators and relations for superalgebras in the finite and twisted affine cases, and also universal central extensions. Afterwards, we apply the FRT formalism to a certain solution of the quantum Yang–Baxter equation to define that new quantum group and we study some of its properties. We construct a functor of Schur–Weyl type which connects it to affine Hecke–Clifford algebras and prove that it provides an equivalence between two categories of modules.     

Orientation-reversing actions on lens spaces and Gaussian integers

A finite group action on a lens space L(p,q) has ‘type OR’ if it reverses orientation and has an invariant Heegaard torus whose sides are interchanged by the orientation-reversing elements. In this paper we enumerate the actions of type OR up to equivalence. This leads to a complete classification of geometric finite group actions on amphicheiral lens spaces L(p,q) with p>2. The family of actions of type OR is partially ordered by lifting actions via covering maps. We show that each connected component of this poset may be described in terms of a subset of the lattice of Gaussian integers ordered by divisibility. This results in a correspondence equating equivalence classes of actions of type OR with pairs of Gaussian integers.     

Lattices of equivalence relations closed under the operations of relation algebras

One of the longstanding problems in universal algebra is the question of which finite lattices are isomorphic to the congruence lattices of finite algebras. This question can be phrased as which finite lattices can be represented as lattices of equivalence relations on finite sets closed under certain first-order formulas. We generalize this question to a different collection of first-order formulas, giving examples to demonstrate that our new question is distinct. We then note that every lattice M _n can be represented in this new way.     

Distinguishability of <Emphasis Type="Italic">s</Emphasis>-labyrinths

In this paper we consider rectangular and s-labyrinths. We investigate problems similar to classical ones in the automata theory, namely, the distinguishability of vertices and the labyrinths equivalence. We prove that for the considered class of labyrinths these problems are solvable and estimate the distinguishing word length. For rectangular labyrinths we prove that the isomorphism and equivalence relations coincide.     

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.