Research On Weighted Automata With Output Based On Strongly Assigned Monoids And Semi-rings

As an important branch of computer science,automata theory provides an im-portant theoretical foundation for computer softwares and hardwares.In order to quantitatively describe some properties of systems in the executive process,the no-tion of weighted automata over semirings is put forward,and its theory and related applications are investagated.Furthermore,M.Droste and I.Meinecke introduced the notion of valuation monoid in 2011,which generalizes the weights of weighted automata to valuation monoids,and they studied the problems of weighted automa-ta in the frame of weights taking in valuation monoids in detail.The weighted finite automata with outputs plays a very important role in natural language processing which is an important research content of automata theory.However,current re-search in this field is rarely involved,which is a motivation for me to study further in this paper.In this paper,we study the properties of S-sequential-like machines over semir-ings,introduce the notions of S-combination over semirings and three types of e-quivalent relationships,irreducibilities and two types of minimalities respectively among S-sequential-like machines,and present various types of relationships among them.By introducing the notion of strong valuation monoids,we give three kinds of weighted machines with outputs in the frame of truth-values taking in a strong valuation monoid.Moreover,we study the relationship between weighted Mealy and weighted Moore machines over strong valuation monoids.The main work is listed as follows:1.Firstly,we introduce the notions of the S-combination and the S-sequential-like machines over semirings,discuss some related properties about S-combination and S-sequential-like machines from the algebraic point.Also,three types of e-quivalence relations of S-sequential-like machines are considered,namely,state-wise,compositewise,and distributionwise equivalence and we show that the last two are equivalent.Moreover,three types of irreducibilities are introduced,namely,statewise,compositewise,and distributionwise irreducibility,and we show that dis-tributionwise irreducibility implies compositewise irreducibility,and compositewise irreducibility implies statewise irreducibility.Finally,we introduce the concepts of statewise minimality and compositewise minimality,show that statewise irreducibil-ity and statewise minimality are equivalent and compositewise minimality implies compositewise irreducibility.2.The notion of strong valuation monoids is introduced,then we define three kinds of weighted machines with outputs,which include weighted sequential ma-chines,weighted Mealy and weighted Moore machines in the frame of weights taking in strong valuation monoids,and investigate their response functions.Furthermore,we study the relationship between weighted Mealy machines and weighted Moore machines over strong valuation monoids and show that weighted sequential machines and weighted Mealy machines introduced here are not equivalent.However,we show that weighted sequential machines and weighted Moore machines defined in this pa-per are equivalent.Thus,the unequivalence between weighted Mealy machines and weighted Moore machines by means of weighted sequential machines over strong valuation monoids is obtained.