| The regular languages which recognized by automata have been applied in the compiler lexical analysis of computer programming, switching circuit design, and so on. And it has played an important role in the theory of formal languages. Since the1960s, scholars have done a lot of work on fuzzy automata and the languages accepted by them. The classical fuzzy automata with membership values in the unit interval [0,1] with max-min composition could recognize only regular languages from the point of view of level structure. To enhance the expressiveness of the fuzzy automata, the membership grades of fuzzy automata were extended to much general lattice structures-lattice-ordered monoids, then the lattice fuzzy automata were proposed. So it is necessary to study the properties of the lattice value fuzzy regular languages.As we all know, it is equivalent for deterministic and non-deterministic classical fuzzy automata, but the similar results are not valid for some lattice-ordered fuzzy automata. The hierarchy of different languages accepted by weighted automata in tropical semiring had been studied by Klimann[24]. In this paper, we introduce the hierarchy of lattice-valued fuzzy regular languages and study their decidability.The arrangement of the paper is as follows:1. According to the hierarchy in weighted automata, first of all, the lattice-valued fuzzy automata will be classified into several types:deterministic, sequential, unambiguous, finitely ambiguous and infinitely ambiguous. Secondly, it is proved that the hierarchy of these lattice fuzzy regular languages has closed connection with the structure of lattice-ordered momoid L, in which the lattice-ordered monoid is commutative. Besides that, we provide a sufficient condition for the equivalence of these several fuzzy regular languages. In particular, some properties of lattice-valued fuzzy regular language when the operation is Archimedean t-norm are also discussed.2. The decidability problem of lattice-valued fuzzy regular languages is dis-cussed. First of all, the several decidability problems of fuzzy regular such as (Eq),(Ineq),(LocalIneq),(LocalEq) are given. Secondly, we can get that there is a rela-tionship with the decidability problem of fuzzy regular languages and the structure of partial order lattice semigroup, i.e., if L is local finiteness, the above several types of the problem are decidable. But if L is not local finiteness, they are not decidable. Finally, we discuss the finite decomposition of finite automata. And it is proved that any Boolen matrix can be decomposed into more than one amalgamation matrix and co-amalgamation matrix, then we decompose the conjugate automata according to this property. |
PDF Full Text Request