有界偏序自动机的同步算法

Synchronizing Algorithms for Bounded Partially Ordered Automata

同步自动机是有同步字的自动机,它们在系统测试、编码、工业自动化、机器人技术及生物计算等领域有着广泛应用。有界偏序自动机是状态集具有与所有输入字母都相容的有界偏序的自动机。文中给出了同步有界偏序自动机的一些重要特征,并据此设计了有界偏序自动机的同步性检测算法、同步字查找算法和最短同步字查找算法,确定了全体n-状态同步自动机的最短同步字长度的上确界。这些工作在有界偏序自动机的范围内解决了同步自动机研究的主要问题。

Synchronizing automata are the automata having a synchronizing word.They have been applied in many fields such as system testing,encoding,industrial automation,robotics and biological computation.Bounded partially ordered automata are the automata whose state set is equipped with a partial order that is compatible to the input letters.This paper reveals some important characterizations of synchronizing bounded partially ordered automata,proposes the algorithms for testing the synchronization,finding a synchronizing word and finding a shortest synchronizing word of an arbitrary bounded partially ordered automaton,and then determines the least upper bound of all n-state synchronizing bounded partially ordered automata.In the field of bounded partially ordered automata,these works solve the main problems on synchronizing automata.