同步有界偏序自动机

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