计算机科学 ›› 2012, Vol. 39 ›› Issue (11): 191-193.

• 人工智能 • 上一篇    下一篇

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

肖芬芳,何勇,胡斌梁,王志喜   

  1. (湖南科技大学计算机科学与工程学院 湘潭411201);(湖南科技大学机电工程学院 湘潭411201)
  • 出版日期:2018-11-16 发布日期:2018-11-16

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

  • Online:2018-11-16 Published:2018-11-16

摘要: 既非陷阱也非强连通的同步自动机称为拟陷阱同步自动机。对于任意的拟陷阱同步自动机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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!