基于强赋值幺半群和半环的带输出加权自动机的研究

【作者】 王敏；

【导师】 李永明；

【作者基本信息】 陕西师范大学 ， 计算机软件与理论， 2018， 硕士

【摘要】 作为计算机科学的一个重要分支,自动机理论为计算机软件、硬件研究提供了重要的基础理论.为了将系统在执行过程中的属性进行定量地描述,人们提出了加权自动机的概念,并对取值于半环的加权自动机理论及其相关应用进行了详细的研究.2011年,M.Droste教授和I.Meinecke教授提出了赋值幺半群的概念,将加权自动机权重的赋值域推广到赋值幺半群上,并对其相关问题进行了详细的研究和阐述.带输出的加权有穷自动机是自动机理论的重要研究内容,它在自然语言的处理等方面有非常重要的作用,目前的研究很少涉及,本文将在此开展工作.本文研究了基于半环的序列机及其性质.通过定义半环上的S-组合、S-序列机,讨论了 S-序列机上的三种等价性之间的关系、S-序列机的三种不可约性之间的关系以及两种极小性与不可约性之间的关系.定义了强赋值幺半群和取值于强赋值幺半群的三种带输出的加权自动机,并研究了强赋值加权Mealy机和强赋值加权Moore机之间的关系.本文的主要工作如下:1.定义了半环上的S-组合、S-序列机,并从代数角度出发研究了 S-组合和S-序列机的相关性质.讨论了S-序列机上的三种等价性,分别是状态等价、复合等价和分布等价,并且对三种等价性分别进行代数的等价刻画,证明了复合等价和分布等价是等价的.而且还讨论了S-序列机的三种不可约性,分别是状态不可约、复合不可约和分布不可约,给出了状态不可约和分布不可约的等价刻画,并得到了分布不可约可推出复合不可约,复合不可约可推出状态不可约.定义了状态极小和复合极小,得到了状态极小和状态不可约是等价的,复合极小可推出复合不可约.2.引入了强赋值幺半群的概念,给出了强赋值加权序列机,强赋值加权Mealy机以及强赋值加权Moore机的定义,并研究了其响应函数.我们证明了强赋值加权序列机与强赋值加权Moore机等价,强赋值加权序列机与强赋值加权Mealy机不等价.从而,以强赋值加权序列机为中介得到了强赋值加权Mealy机与强赋值加权Moore机不等价.更多还原

【Abstract】 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.更多还原