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

On the Synchronizing Problem of Tree-Like Partially Ordered Automata

作　　者：崔振河 王志喜[2,3] 何勇 CUI Zhen-He;WANG Zhi-Xi;HE Yong(School of Computer Science and Engineering,Sun Yat-Sen University,Guangzhou 510006;School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201;Key Laboratory of Service Computing and New Technologies of Software Service of Hunan Province,Xiangtan,Hunan 411201)

机构地区：[1]中山大学计算机学院,广州510006 [2]湖南科技大学计算机科学与工程学院,湖南湘潭411201 [3]服务计算与软件服务新技术湖南省重点实验室,湖南湘潭411201

出　　处：《计算机学报》2023年第9期1961-1976,共16页Chinese Journal of Computers

基　　金：国家自然科学基金(No.61572013)资助。

摘　　要：对于给定的自动机,能将所有状态都转换到同一状态的输入字被称为该自动机的同步字.有同步字的自动机称为同步自动机.同步自动机已广泛应用于系统测试、编码、工业自动化、机器人技术及生物计算等领域.同步自动机研究的基本问题是自动机的同步问题(含同步性判定问题和同步字查找问题),最具挑战性的课题是证实或证伪关于同步自动机最短同步字长度的Cerny猜想.偏序自动机是具有一个相容偏序结构的自动机.同步自动机的研究从理论上可以归结到同步偏序自动机的研究上,因此,Cerny猜想成立当且仅当其对所有的偏序自动机都成立.现有的研究工作表明,Cerny猜想只对于一些结构较为特殊的偏序自动机类,包括单演自动机、广义单演自动机以及有界偏序自动机是成立的.作为偏序自动机的另一类特殊情形,本文研究关于树形偏序自动机的同步性检测问题,同步字查找问题以及Cerny猜想,主要贡献包括:讨论了树形偏序自动机与现有的几类偏序自动机之间的关系,说明了树形偏序自动机包含所有单演自动机和有界偏序自动机,并且不同于广义单演自动机类;给出了树形偏序自动机的同步性判定和同步字计算方法,特别地,证明了Cerny猜想对树形偏序自动机成立;设计了树形偏序自动机的专用同步算法,该算法的时间复杂度低于通用的自动机同步算法,且对任意n-状态同步树形偏序自动机都可以找到长度不超过(n-1)^(2)的同步字.An input word of an automaton is called a synchronizing word if it transfers all states to a single state.An automaton having a synchronizing word is called a synchronizing automaton.Synchronizing automata have been validly applied in many fields such as system testing,encoding,industrial automation,robotics and biological computation.For the researches on synchronizing automata,the fundamental problem is the synchronizing problem,while the most challenging issue is to prove or disapprove the Cerny Conjecture concerning the lengths of the shortest synchronizing words of synchronizing automata.Partially ordered automata(in brief,po-automata)are the automata whose state set is equipped with a partial order that compatible to the input letters.Theoretically,the research of synchronizing automata can be ascribed to the research of synchronizing po-automata,thus,Cerny Conjecture holds precisely when it holds for partially or dered automata.Some classes of po-automata,such as monotonic automata,generalized mono-tonic automata and bounded po-automata,have been proved to satisfy Cerny Conjecture.Tree-like po-automata are the po-automata whose partially ordered state set is tree-like,in order to ex-tend the research of Cerny Conjecture to a more general case of po-automata,this paper considers the synchronization of tree-like po-automata.A method to check the synchronization and find a synchronizing word(when it exists)for an arbitrary tree-like po-automaton is invented.With the application of such a method,the Cerny Conjecture is confirmed for tree-like po-automata,and a synchronizing algorithm for tree-like po-automata is designed.Particullarly,compared with the general synchronizing algorithms,the current algorithm has the lower time and space complexi-ties,and it can find a synchronizing word for an n-state synchronizing tree-like po-automaton un-der the restriction of length at most(n-1)^(2).

关 键 词：同步自动机 同步算法 Cerny猜想 相容偏序结构 树形偏序自动机 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]