强赋值幺半群上的加权Mealy机与加权Moore机的关系  

Relationship Between Weighted Mealy and Weighted Moore Machines over Strong Valuation Monoids

作　　者：王敏 李永明[1] WANG Min, LI Yongming(College of Computer Science, Shaanxi Normal University, Xi＇an 710119, Chin)

机构地区：[1]陕西师范大学计算机科学学院,西安710119

出　　处：《计算机科学与探索》2018年第8期1331-1338,共8页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.11671244~~

摘　　要：赋值幺半群是一类包含半环在内的代数结构,在赋值幺半群的基础上定义强赋值幺半群。由于带输出的加权有穷自动机在自然语言的处理方面有很重要的意义,是自动机理论的一个重要研究方向。在权重取值于强赋值幺半群下定义了3种带输出的加权自动机,即强赋值加权序列机、强赋值加权Mealy机以及强赋值加权Moore机,并且给出了它们的响应函数,进而探讨了强赋值加权Mealy机和强赋值加权Moore机的关系,即强赋值加权序列机与强赋值加权Mealy机是不等价的,强赋值加权序列机与强赋值加权Moore机是等价的;并以强赋值加权序列机为中介,强赋值加权Mealy机与强赋值加权Moore机的关系是不等价的。Valuation monoids are a class of algebraic structures subsuming a range of models as well as semirings. The notion of strong valuation monoids is introduced. The weighted finite automaton with outputs plays a very impor- tant role in natural language processing which is an important research direction of automata theory. This paper introduces three kinds of weighted machines with outputs, which include -weighted sequential machines, weighted Mealy and weighted Moore machines, in the frame of weights taking in strong valuation monoids, and proposes their response functions. Then this paper studies the relationship between weighted Mealy and weighted Moore machines over strong valuation monoids. Weighted sequential machines and weighted Mealy machines introduced here are not equivalent. However, weighted sequential machines and weighted Moore machines defined in this paper are equivalent. The unequivalence between weighted Mealy machines and weighted Moore machines by means of weighted sequential machines over strong valuation monoids is obtained.

关 键 词：强赋值幺半群 强赋值加权序列机 强赋值加权Mealy机 强赋值加权Moore机 等价性 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]