拟陷阱同步自动机的最短同步字的长度  

Length of the Shortest Synchronizing Words for Quasi-trapped Synchronizing Automata

作　　者：肖芬芳[1] 何勇[1] 胡斌梁[2] 王志喜[1] 

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

出　　处：《计算机科学》2012年第11期191-193,共3页Computer Science

基　　金：国家自然科学基金(61272196);湖南省自然科学基金(06A2025);湖南省普通高校创新平台开放基金(09K084);湖南省教育厅科学基金(10C0692)资助

摘　　要：既非陷阱也非强连通的同步自动机称为拟陷阱同步自动机。对于任意的拟陷阱同步自动机A,利用其强连通子自动机的状态数给出了A的最短同步字的长度的一个上界,进而获得了A满足C∨ern猜想的一个充分条件。A synchronizing automaton is said to be quasi-trapped if it is neither trapped nor strongly connected.Let A be a quasi-trapped synchronizing automaton.By using the number of the states of the strongly connected sub-automaton of A,a upper bound of the length of the shortest synchronizing word of A was given,and then a sufficient condition for A to satisfy the Cerny Conjecture was obtained.

关 键 词：拟陷阱同步自动机 陷阱同步自动机 最短同步字 强连通子自动机 C∨ern猜想 

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