摘要
同步自动机是有同步字的自动机,它们在系统测试、编码、工业自动化、机器人技术及生物计算等领域有着广泛应用。有界偏序自动机是状态集具有与所有输入字母都相容的有界偏序的自动机。文中给出了同步有界偏序自动机的一些重要特征,并据此设计了有界偏序自动机的同步性检测算法、同步字查找算法和最短同步字查找算法,确定了全体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.
作者
王志喜
蒋贵德
WANG Zhixi;JIANG Guide(School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China)
出处
《计算机科学》
CSCD
北大核心
2023年第S01期831-835,共5页
Computer Science
基金
国家自然科学基金(61572013)。
关键词
同步自动机
有界偏序自动机
同步性检测算法
同步字查找算法
最短同步字查找算法
Synchronizing automaton
Bounded partially ordered automata
Algorithm for testing synchronization
Algorithm for finding a synchronizing word
Algorithm for finding a shortest synchronizing word