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

Synchronizing Algorithms for Bounded Partially Ordered Automata

作　　者：王志喜[1] 蒋贵德 WANG Zhixi;JIANG Guide(School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China)

机构地区：[1]湖南科技大学计算机科学与工程学院,湖南湘潭411201

出　　处：《计算机科学》2023年第S01期831-835,共5页Computer Science

基　　金：国家自然科学基金(61572013)。

摘　　要：同步自动机是有同步字的自动机,它们在系统测试、编码、工业自动化、机器人技术及生物计算等领域有着广泛应用。有界偏序自动机是状态集具有与所有输入字母都相容的有界偏序的自动机。文中给出了同步有界偏序自动机的一些重要特征,并据此设计了有界偏序自动机的同步性检测算法、同步字查找算法和最短同步字查找算法,确定了全体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.

关 键 词：同步自动机 有界偏序自动机 同步性检测算法 同步字查找算法 最短同步字查找算法 

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