同步有界偏序自动机

• 作者: 何勇 孙士远 崔振河
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 同步自动机 最短同步字 (C)ern(y)猜想 有界偏序自动机 格序自动机
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 人工智能
• 页码范围: 610-623
• 页数: 14页
• 分类号: TP301
• 字数: 10133字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2019.00610

摘要

所有状态都能被同一个字转换到同一状态(完全确定有限状态)的自动机称为同步自动机.同步自动机在许多方面都有着广泛的应用,如重启装置的设计、系统测试、编码、工业自动化、机器人技术以及生物计算等.同步自动机研究的最基本的问题是自动机的同步性问题,同步性问题主要包括同步性检测和同步字查找.最短同步字问题是同步自动机研究的核心课题,关于这个问题,(C)ern(y)提出了如下猜想:所有n-状态同步自动机的最短同步字长度的上确界为(n-1)2.现有研究结果表明,对于某些特殊类型的自动机(C)ern(y)猜想是成立的,例如循环自动机、欧拉自动机等.然而,对于一般的同步自动机(C)ern(y)猜想尚未得到证实或否定.由于任何自动机都能看作偏序自动机,因而(C)ern(y)猜想成立的充分必要条件是它对所有偏序自动机都成立.单演自动机和广义单演自动机等偏序自动机都已被证实满足(C)ern(y)猜想.作为偏序自动机的另一类特殊情形,该文定义了有界偏序自动机,运用组合分析方法证明了n-状态有界偏序自动机最短同步字的长度为n-1.作为主要结果的推论,得出n-状态格序自动机的最短同步字的长度也是n-1.这就意味着有界偏序自动机(特别是格序自动机)满足(C)ern(y)猜想.进一步地,该文设计了有界偏序自动机的同步性检测及同步字查找算法.最后,该文还对单演自动机、广义单演自动机和有界偏序自动机的关系进行了讨论,得出以下结论:广义单演自动机和有界偏序自动机同为单演自动机的真推广,且它们的表达能力不相容.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何勇	湖南科技大学计算机科学与工程学院	19	42	4.0	6.0
2	崔振河	湖南科技大学计算机科学与工程学院	1	2	1.0	1.0
3	孙士远	湖南科技大学计算机科学与工程学院	2	2	1.0	1.0