Algebraic Properties And Minimization Algorithm Of Lattice-valued Fuzzy Finite State Automata

Automata with truth-values in lattice-ordered monoid are more powerful than other kind of fuzzy automata, which-construct a new model of computing with words.Therefore,the study of the the algebraic properties of automata with truth-values in lattice-ordered monoid and the study of the minimization algorithm form two crucial subjects in fuzzy automata theory.Now that the L-valued fuzzy state automata has such powerful computation capacity, it is necessary to traverse the algebraic properties such as transformation semigroups,products and covering relations in L-valued fuzzy automata in order to show the close correspondence between the algebraic properties and the latticeordered monoid.As for a given automata,there exists three cases:for some state which did not being visited, for some state itself indeed being not reachable although it has been visited,for some state it is equivalent to other states though it can be reached to, in these three cases it is obviously redundant to construct these automata, and the only way for us is to delete,integrate and reduct these useless states in order to minimize the number of states.If a given automata which can be minimizated,whether can we find an effective algorithm to minimize them?In this thesis,we mainly study the algebraic properties and minimization algorithm of L-valued fuzzy finite state automata which are based on the references [3, 5, 8, 13 - 17, 29 - 30, 39].Firstly,we introduce the concepts of lattice-valued(abbreviated as L-valued) fuzzy finite state automata and L-valued fuzzy transformation semigroups, traverse the algebraic properties of them. Unlike the case of ordinary and classical fuzzy automata theory,we give sufficient and necessary conditions for a given L-valued fuzzy finite state automata to form a fuzzy transformation semigroup.Furthermore we introduce the concepts of coverings and lattice-valued homomorphisms,we prove that the L-valued fuzzy transformation semigroups in which the multiplication is fuzzy transformation semigroup inducible is equivelent to usual faithful transformation semigroups in the sence of lattice-valued strong homomorphism.In the end,we give four ways to constructing products of L-valued fuzzy finite state automata and two ways to constructing products of L-valued fuzzy transformation semigroups and algebraic properties and covering relation of these products are also studied.Secondly, in a more generalized framestructrue--lattice-ordered monoids,the notion of lattice-valued Mealy-type automata is introduced,we traverse some algebraic properties of this automata and investigate the congruences and homomorphisms of this type automata.Our main results indicate that the algebraic properties of lattice-valued Mealy-type automata have Close links to the algebraic properties of lattice-ordered monoids which automata take values in.Futhermore we study the minimization of lattice-valued Mealy-type automata and provide an algorithm to achieve the minimal lattice-valued Mealy-type automata within finite steps.Finally, as an application,we study the second type of L-valued fuzzy finite state automata which has fuzzy initial state and fuzzy final state, and provide an algorithm to achieve the minimal L-valued fuzzy finite state automata within finite steps in the regular congruence relations.