Research On Topology And Algebraic Features Of Weighted Automata

Automata are the simplest mathematical model in computational theory,and au-tomata theory plays an important role in classical computational theory.Weighted au-tomata are one of the most widely used automata models.Weighted automata can be applied to classical automata,probabilistic automata,fuzzy automata,or even quantum automata with respect to different structures of the weight(semigroups).And there is a close relationship between languages theory and theory of automata.Regular languages,as the languages accepted by finite automata,are widely used in natural language pro-cessing,speech recognition and model checking.Based on some special semirings(for example,fuzzy semirings,([0,1],max,min,0,1)or lattice semigroups),and some gen-eral semirings,this thesis gradually studies the algebraic theory of weighted automata as well as the languages accepted by weighted automata.The research mainly focuses on the following aspects:topological characterization for fuzzy regular languages,mini-mization of lattice-valued multiset finite automata,and variety theory of weighted finite automata.The main contributions in this thesis are listed as follows:(1)We systematically investigate the relationship between regular languages and clopen subsets of Profinite topological space.We introduce the concepts of lower semi-continuous functions as well as the induced fuzzy topological space of Profinite topo-logical space,and discuss the relationship between fuzzy regular languages and lower semicontinuous functions.We present a topological characterization for fuzzy regular languages based on the characteristics of fuzzy regular languages,and establish a bijec-tive correspondence between the class of fuzzy regular languages and the set of all clopen fuzzy subsets with finite image in the induced fuzzy topological space of Profinite topo-logical space.Moreover,we give a decomposition representation of any closed fuzzy subset in the induced fuzzy topological space via fuzzy regular languages.These results are presented in chapter 3.(2)We discuss lattice multiset finite automata and languages accepted by lattice multiset finite automata.We present some operations on lattice-valued regular multi-set languages,and prove that the family of lattice-valued regular multiset languages is closed under these operations.We establish the equivalence of(nondeterministic)lat-tice multiset finite automata and deterministic lattice multiset finite automata,and study the minimization problem of deterministic lattice multiset finite automata.We present an effective algorithm to obtain a minimal deterministic lattice multiset finite automata for a given lattice multiset finite automata.Finally,we give a decomposition of lattice-valued regular multiset languages accepted by some special minimal deterministic lattice multiset finite automata.These results are presented in chapter 4.(3)According to some special structures of semirings,we introduce the concept of monoid for some weighted finite automata,and study the condition for syntactic monoids being finite for weighted finite automata.We establish a bijective correspondence be-tween transformation semigroups and syntactic monoids.We discuss the properties of states transition function of weighed finite automata under different products,and then we establish a relationship between weighted finite automata under the direct product(cascade product)and the corresponding quotient transformation semigroups.These re-sults are presented in chapter 5.(4)We investigate the minimization of weighted finite automata and varieties of regular series.We introduce the concepts of quotients of formal power series,and discuss the basic properties of syntactic monoids.We present the Myhill-Nerode theorem for formal power series.Finally,we introduce the concepts of varieties of regular series and varieties of finite monoids,and then we establish a relationship between varieties of regular series and varieties of finite monoids.These results are presented in chapter 6.