同步有界偏序自动机

Synchronizing Bounded Partially Ordered Automata

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

An(completely deterministic finite state)automaton is synchronizing if its states can be transited to a single state under the action of the same word,which is called synchronizing word.Synchronizing automata has been widely used in many fields such as the design of restart device,system testing,encoding,industrial automation,robotics and biological computation.The synchronization problem is the basic problem of synchronizing automata research,which includes synchronization detection and finding synchronizing words,the former is aimed at discussing how to determine whether an automaton is synchronizing and the latter mainly studies how to find shorter synchronizing words(preferably the shortest synchronizing words)as quickly as possible.The problem of the shortest synchronizing word is the core problem of synchronizing automaton,with respect to this problem,ˇCernconjectured that each n-state synchronizing automaton possesses a synchronizing word of length at most(n-1)2.Such a conjecture is calledˇCernconjecture.Some special class of automata such as circular automaton,Eulerian automaton,aperiodic automaton has been proved to satisfyˇCernConjecture.However,this conjecture has not yet been confirmed or denied for general synchronizing automata so far,and it has become one of the open problems in automata theory.Partially ordered automata are the automata whose state sets are equipped with a partial order relation that compatible to the input letters.Since each automaton can be dealt with a partially ordered automaton,ˇCernConjecture holds precisely when it holds for partially ordered automata.Some classes of partially ordered automata such as monotonic automata and generalized monotonic automata have been proved to satisfyˇCernConjecture.As a kind of special cases of partially ordered automata,bounded partially ordered automata are defined.In the aids of combinatoric analyses,it is shown that the shortest synchronizing words of an-state synchronizing bounded partially ordered automaton are of length at most n-1.As an immediate consequence,the shortest synchronizing words of a n-state synchronizing latticeordered automaton are also of length at most n-1.This means that bounded partially ordered automata(especially,lattice-ordered automata)satisfyˇCernconjecture.Furthermore,an algorithm is proposed for checking the synchronization and finding a shortest synchronizing word of a bounded partially ordered automaton.Also,the relationships of the classes of monotonic automata,generalized monotonic automata and bounded partially ordered automata are discussed.It is illustrated that both the classes of generalized monotonic automata and that of bounded partially ordered automata are proper generalizations of the class of monotonic automata which have distinct expression abilities.