Abstract: 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 important 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.

Key words: strong valuation monoids, weighted sequential machines, weighted Mealy machines, weighted Moore machines, equivalence

摘要： 赋值幺半群是一类包含半环在内的代数结构，在赋值幺半群的基础上定义强赋值幺半群。由于带输出的加权有穷自动机在自然语言的处理方面有很重要的意义，是自动机理论的一个重要研究方向。在权重取值于强赋值幺半群下定义了3种带输出的加权自动机，即强赋值加权序列机、强赋值加权Mealy机以及强赋值加权Moore机，并且给出了它们的响应函数，进而探讨了强赋值加权Mealy机和强赋值加权Moore机的关系，即强赋值加权序列机与强赋值加权Mealy机是不等价的，强赋值加权序列机与强赋值加权Moore机是等价的；并以强赋值加权序列机为中介，强赋值加权Mealy机与强赋值加权Moore机的关系是不等价的。

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