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

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