概率有限状态自动机的代数性质  

Algebraic Properties of Probabilistic Finite State Automata

作　　者：谢正卫[1] 翟莹[2] 邓培民[2] 易忠[3] 

机构地区：[1]江苏理工学院数理学院,江苏常州213001 [2]广西师范大学数学科学学院,广西桂林541004 [3]广西民族师范学院数学与计算机科学系,广西崇左532200

出　　处：《计算机研究与发展》2013年第12期2691-2698,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(11161005);广西自然科学基金项目(2010GXNSFA013118);广西教育厅科研项目(桂教科研[2009]25号);广西教育厅自然科学基金项目(201106LX074)

摘　　要：利用矩阵、同态、同构、同余等代数工具研究概率有限状态自动机的代数性质.首先定义了输入集上两个字符串同余的概念,并利用概率转移矩阵给出2个字符串同余的一些等价刻画.进而提出概率有限状态自动机同态和同构的概念,并给出了概率有限状态自动机同态定理.证明了2个概率有限状态自动机同构的充要条件是它们的概率转移矩阵可以通过第1种行列初等变换相互转化;同时提出了2个概率有限状态自动机积与和的概念,并得到了积自动机、和自动机的同态关系.最后将模糊自动机中交换的概念引入到概率有限状态自动机中,并利用概率转移矩阵给出了此类自动机交换的一些等价刻画以及和自动机、积自动机交换的充要条件.Probabilistic finite state automata（PFA）is widely used today in a variety of areas in pattern recognition, or in fields to which pattern recognition is linked, computational linguistics, machine learning, time series analysis, circuit testing, computational biology, speech recognition, and machine translation are some of them. In this paper, algebraic properties of PFA are studied by using algebraic tools such as matrices, homomorphisms, isomorphisms, congruences, and so on. Firstly, the concept of congruences of two strings over input alphabet is defined, and some equivalent characterizations of congruences of two strings are given by probabilistic transition matrices. Secondly, notions of homomorphisms and isomorphisms of PFA are introduced, and homomorphism theorem of PFA is shown. It is also proved that two PFA are isomorphic if and only if their probabilistic transition matrices can be transformed into each other by the first kind of elementary transformation of rows and columns. The concept of products and sums of PFA is defined, and the homomorphism relationships between products and sums o{ PF finite state machines is introduced of PFA are obtained as well as the and sums of PFA by probabilistic A are investigated. Finally, the concept of commutativity of fuzzy for PFA, and several equivalent characterizations of commutativity sufficient and necessary conditions of the commutativity of products transition matrices.

关 键 词：概率有限状态自动机 概率转移矩阵 同余 同态 同构 交换 

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