计算机科学 ›› 2012, Vol. 39 ›› Issue (11): 191-193.
• 人工智能 • 上一篇 下一篇
肖芬芳,何勇,胡斌梁,王志喜
出版日期:
发布日期:
Online:
Published:
摘要: 既非陷阱也非强连通的同步自动机称为拟陷阱同步自动机。对于任意的拟陷阱同步自动机A,利用其强连 通子自动机的状态数给出了A的最短同步字的长度的一个上界,进而获得了A满足Lcrny猜想的一个充分条件。
关键词: 拟陷阱同步自动机,陷阱同步自动机,最短同步字,强连通子自动机,亡crny猜想
Abstract: 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 sulrautomaton 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.
Key words: Quasi trapped synchronizing automaton, Trapped synchronizing automaton, Shortest synchronizing word,Strongly conncctcd sub-automaton,}crny conjccturc
肖芬芳,何勇,胡斌梁,王志喜. 拟陷阱同步自动机的最短同步字的长度[J]. 计算机科学, 2012, 39(11): 191-193. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2012/V39/I11/191
Cited