科研之友
微信
新浪微博
Facebook
分享链接
摘要
对于给定的自动机,能将所有状态都转换到同一状态的输入字被称为该自动机的同步字.有同步字的自动机称为同步自动机.同步自动机已广泛应用于系统测试、编码、工业自动化、机器人技术及生物计算等领域.同步自动机研究的基本问题是自动机的同步问题(含同步性判定问题和同步字查找问题),最具挑战性的课题是证实或证伪关于同步自动机最短同步字长度的■猜想.偏序自动机是具有一个相容偏序结构的自动机.同步自动机的研究从理论上可以归结到同步偏序自动机的研究上,因此,■猜想成立当且仅当其对所有的偏序自动机都成立.现有的研究工作表明,■猜想只对于一些结构较为特殊的偏序自动机类,包括单演自动机、广义单演自动机以及有界偏序自动机是成立的.作为偏序自动机的另一类特殊情形,本文研究关于树形偏序自动机的同步性检测问题,同步字查找问题以及■猜想,主要贡献包括:讨论了树形偏序自动机与现有的几类偏序自动机之间的关系,说明了树形偏序自动机包含所有单演自动机和有界偏序自动机,并且不同于广义单演自动机类;给出了树形偏序自动机的同步性判定和同步字计算方法,特别地,证明了■猜想对树形偏序自动机成立;设计了树形偏序自动机的专用同步算法,该算法的时间复杂度低于通用的自动机同步算法,且对任意n-状态同步树形偏序自动机都可以找到长度不超过(n-1)2的同步字.
- 单位
