树形偏序自动机的同步问题

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

同步有界偏序自动机

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

同步链与纯正非同步半群

通过合理转化自动机与变换半群的定义提出同步链的概念,证明了一些类型的变换半群满足Cerny猜想,并部分刻画了一类不满足Cerny猜想的变换半群,即纯正非同步半群.

Some Aspects of Synchronization of DFA

A word w is called synchronizing （recurrent, reset, directable） word of deterministic finite automata （DFA） if w brings all states of the automaton to a unique state. According to the famous conjecture of Cerny from 1964, every n-state synchronizing automaton possesses a synchronizing word of length at most （n - 1）2. The problem is still open. It will be proved that the Cerny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every n-state （n 〉 2） synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than （n - 1）2/2. The last important class of DFA involved and studied by Schutzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established.