文献类型：期刊文章

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

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

出　　处：《计算机研究与发展》

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

年　　份：2013

卷　　号：50

期　　号：12

起止页码：2691-2698

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CSA-PROQEUST、CSCD、CSCD2013_2014、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：利用矩阵、同态、同构、同余等代数工具研究概率有限状态自动机的代数性质.首先定义了输入集上两个字符串同余的概念,并利用概率转移矩阵给出2个字符串同余的一些等价刻画.进而提出概率有限状态自动机同态和同构的概念,并给出了概率有限状态自动机同态定理.证明了2个概率有限状态自动机同构的充要条件是它们的概率转移矩阵可以通过第1种行列初等变换相互转化;同时提出了2个概率有限状态自动机积与和的概念,并得到了积自动机、和自动机的同态关系.最后将模糊自动机中交换的概念引入到概率有限状态自动机中,并利用概率转移矩阵给出了此类自动机交换的一些等价刻画以及和自动机、积自动机交换的充要条件.

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

分 类 号：TP301.1] O153[计算机类]