• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

Weighted regular grammars over valuation monoid  

ZHAO Fei,LI Yong-ming   

  1. (College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119,China)
  • Received:2015-12-20 Revised:2016-03-13 Online:2016-07-25 Published:2016-07-25

Abstract:

Regular grammars are necessary tools for the analysis of automata.  We introduce the concepts of weighted regular grammars and weighted similar regular grammars over valuation monoid, discuss the relationships among weighted regular grammar, weighted similar regular grammar and weighted finite automata (WFA). We show that for a given weighted regular grammar or a weighted similar regular grammar, their there is a WFA which is equivalent to the weighted regular grammar or the weighted similar regular grammar.  We define the concept of distributable valuation monoids  and prove that on a distributable valuation monoid  for a given WFA  there is a weighted regular grammar or a weighted similar regular grammar, and they generate the same languages. Examples show that the distributivity of valuation monoid is not a given WFA  and we can find a weighted regular grammar or a weighted similar regular grammar which is equivalent to the WFA.

Key words: valuation monoid, weighted regular grammar, weighted finite automata