概率有限自动机积的覆盖性
198 浏览量
2020-06-14
19:23:44
上传
评论
收藏 244KB PDF 举报
第
32
卷 第
4
期
2017
年
12
月
湖南科技大学学报
（
自然科学版
）
Journal of Hunan University of Science ＆ Technology（ Natural Science Edition）
Vol．32 No．4
Dec． 2017
doi： 10．13582 /j．cnki．1672
－
9102．2017．04．017
概率有限自动机积的覆盖性
①
杨京开
1，2
，
蔡永裕
3
，
程裕强
1
，
黄飞丹
4
（ 1．
玉林师范学院
数学与统计学院
，
广西 玉林
537000；
2．
玉林师
范学院 广西高校复杂系统优化与大数据处理重点实验室
，
广西 玉林
537000；
3．
湖南科技大学 数学与计算科学学院
，
湖南 湘潭
411201；
4．
贵州工程应用技术学院 理学院
，
贵州 毕节
551700）
摘 要
：
提出了概率有限自动机的覆盖的定义
，
然后利用代数的方法讨论了概率有限自动机的全直积
（
限制直
积
） 、
级
联积
、
圈积
、
并积的覆盖关系
，
证明了
2
个概率有限自动机的级联积
（
限制直积
）
覆盖它们的圈积
（
全直积
） ，
概率有限自动
机的圈积的全直积覆盖它们的全直积的圈积
，
给出了概率有限自动机的弱同态与覆盖的关系
，
研究了概率有限自动机的积
的覆盖关系的传递性质
．
关键词
：
概率有限自动机
；
积
；
覆盖
；
同态
中图分类号
： TP301．1
文献标志码
： A
文章编号
： 1672
－
9102（ 2017） 04
－
0112
－
06
On covering of products of probabilistic finite automata
Yang Jingkai
1，2
，Cai Yongyu
3
，Cheng Yuqiang
1
，Huang Feidan
4
（ 1． College of Mathematics and Statistics，Yulin Normal University，Yulin 537000，China；
2． Guangxi Colleges and Universities Key Laboratory of Complex System Optimization and Large Data Processing，
Yulin Normal University ，Yulin 537000，China；
3． College of Mathematics and Computational Science，Hunan University of Science and Technology，Xiangtan 411201，China；
4． School of Science，Guizhou University of Engineering Science，Bijie 551700，China）
Abstract： The concept of covering of probabilistic finite automata was introduced，covering relationship on
several kinds of products of probabilistic finite automata，such as full direct product（ restricted direct product）
，
cascade product，wreat
h product and join were discussed，it was proved that the cascade product （ restricted
direct product） of two probabilistic finite automata covered their wreath product（ full direct product） ，full direct
product of wreath product of probabilistic finite automata covered their wreath product of full direct product，the
relations between weak homomorphism of probabilistic finite automata and covering of probabilistic finite automata
were given，transitivity of covering of product of probabilistic finite automata were investigated．
Keywords： probabilistic finite automata； product； covering； homomorphism
概率有限自动机是自动机理论的一个主要研究领域
，
作为确定型有限自动机的推广
，
概率有限自动机
在
计算机科学
、
人工
智能
、
离散事件系统等领域得到了广泛的应用
．
目前
，
对于概率自动机的研究主要是其
应用方面
，
集中在突变测试
、PAC
－
可学性
、
概率离散事件系统
、
基于小波变换的特征提取等
［1
－
4］
．
对概率有
限自动机的代数结构
、
代数性质还没有进行深入系统的研究
．
这在理论上是个大的缺陷
，
对它们的具体应
用有很大的影响
．
因此
，
利用代数学中的理论和思想方法研究概率有限自动机具有十分重要的意义
．
①
收稿日期
： 2015
－
09
－
08
基金项目
：
广西
自然科学基金资助项目
（ 2014GXNSFBA118018 ； 2016GXNSFBA380165） ；
广西高校复杂系统优化与大数据处理重点实
验室开放基金资助项目
（ 2015CSOBDP0104） ；
贵州省科技合作计划资助项目
（
黔科合
LH
字
［2016］7062
号
）
通信作者
：
蔡永裕
（ 1956
－
） ，
男
，
湖南株洲人
，
副教授
，
主要从事代数学研究
． E
－
mail： yongyucai@163．com
中国煤炭期刊网
www.chinacaj.net
资源评论
