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

Algebraic Properties of Probabilistic Finite Automata

作　　者：杨京开[1,2] 黄秋娇 李芳[1] 陈彩虹[1] 

机构地区：[1]玉林师范学院数学与信息科学学院,广西玉林537000 [2]玉林师范学院广西高校复杂系统优化与大数据处理重点实验室,广西玉林537000

出　　处：《数学的实践与认识》2016年第8期238-248,共11页Mathematics in Practice and Theory

基　　金：广西自然科学基金资助(2014GXNSFBA118018);广西高校复杂系统优化与大数据处理重点实验室开放基金资助(2015CSOBDP0104);广西壮族自治区大学生创新创业训练计划立项项目资助(201510606092)

摘　　要：研究了概率有限自动机的同态(弱同态)、有效划分等代数性质.首先,提出了完全的、不可约的概率有限自动机,概率有限自动机的并积等概念.然后,讨论了两个概率有限自动机的级联积、圈积、并积的有效划分与其因子的有效划分之间的关系,证明了在一定条件下两个概率有限自动机的级联积(并积)的商概率有限自动机与其因子的商概率有限自动机的级联积(并积)是相等的.最后,得到了概率有限自动机的极大有效划分的一个刻画.In this paper,algebraic properties such as homomorphism（weak homomorphism）,effectively partition of probabilistic finite automata are investigated.Firstly,the concepts of complete and irreducible probabilistic finite automata,join of probabilistic finite automata and so on are put forward.Then,the relationship between the effectively partitions of cascade product,wreath product,join of probabilistic finite automata and their factors are given,quotient probabilistic finite automata of cascade product（join） of probabilistic finite automata is equal to cascade product（join） of their factor＇ s quotient probabilistic finite automata under certain conditions is proved.Finally,a characterization on maximum effectively partition of probabilistic finite automata is obtained.

关 键 词：概率有限自动机 商概率有限自动机 积 同态 有效划分 

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