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

• 作者: 易忠 翟莹 谢正卫 邓培民
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 概率有限状态自动机 概率转移矩阵 同余 同态 同构 交换
• 年，卷（期）: 2013,（12）
• 所属期刊栏目: 计算机科学理论
• 页码范围: 2691-2698
• 页数: 8页
• 分类号: TP301.1|O153
• 字数: 6909字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邓培民	广西师范大学数学科学学院	61	278	9.0	13.0
2	翟莹	广西师范大学数学科学学院	12	38	4.0	6.0
3	易忠	广西民族师范学院数学与计算机科学系	9	22	3.0	4.0
4	谢正卫	江苏理工学院数理学院	5	20	2.0	4.0