• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Mathematical Foundations of Computer Science >An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Cerny Conjecture
【24h】

An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Cerny Conjecture

机译：有效的算法发现了有关Cerny猜想的明显趋势和示例

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A word w is called synchronizing (recurrent, reset, directed) word of a deterministic finite automaton (DFA) if w sends all states of the automaton on a unique state. Jan Cerny had found in 1964 a sequence of n-state complete DFA with shortest synchronizing word of length (n — 1)~2. He had conjectured that it is an upper bound for the length of the shortest synchronizing word for any n-state complete DFA. The examples of DFA with shortest synchronizing word of length (n — 1)~2 are relatively rare. To the Cerny sequence were added in all examples of Cerny, Piricka and Rosenauerova (1971), of Kari (2001) and of Roman (2004). By help of a program based on some effective algorithms, a wide class of automata of size less than 11 was checked. The order of the algorithm finding synchronizing word is quadratic for overwhelming majority of known to date automata. Some new examples of n-state DFA with minimal synchronizing word of length (n — 1)~2 were discovered. The program recognized some remarkable trends concerning the length of the minimal synchronizing word.
机译：如果W在唯一状态下将AutomatOn的所有状态发送所有状态，则单词W称为同步（重新发生，重置，定向）字（DFA）。 Jan Cerny于1964年发现了一系列N状态，具有最短的同步长度（n - 1）〜2。他猜想它是任何N状态的最短同步词的长度的上限。具有最短同步长度（n - 1）〜2的DFA的示例相对罕见。在Cerny，Piricka和Rosenauerova（1971）的所有例子中，在Kari（2001）和罗马（2004）中加入了Cerny序列。通过基于某些有效算法的程序的帮助，检查了大于11的宽的自动机。查找同步字的算法顺序对于迄今为止的Automata已知的绝大多数是二次数据。发现具有最小同步长度（n - 1）〜2的n状态DFA的一些新示例。该计划认识到关于最小同步字的长度的一些显着趋势。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号