加权有穷自动机的代数性质  

Algebraic properties of weighted finite state automata

作　　者：张丽霞[1] 

机构地区：[1]安庆师范学院数学与计算科学学院,安徽安庆246013

出　　处：《计算机工程与科学》2014年第11期2186-2190,共5页Computer Engineering & Science

基　　金：安庆师范学院青年科研基金项目(KJ201214);安徽省优秀青年人才基金项目(2011SQRL097)

摘　　要：在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。On the basis of the theory of weighted finite automata,we prove the computing equivalence between two weighted finite automatas under the strong homomorphism of weighted finite automatas,and obtain the quotient weighted automata by establishing the equivalence relation on the states of weighted finite automata.Based on the equivalence relation,the equivalence between weighted finite automata and its quotient automata is also proved.Specifically,the concepts such as commutability,separateness,（strong） connectedness properties and layers of weighted finite automata are introduced,and their relations in two different weighted finite automata are discussed under the homomorphism or strong homomorphism.

关 键 词：形式幂级数 加权有穷自动机 同态 强连通 

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