A. N. Trahtman. Modifying the upper bound on the length of minimal synchronizing word

Natural Sciences / Computer Science / Automata theory

Submitted on: Mar 31, 2012, 20:12:43

Description: A word w is called synchronizing (recurrent, reset, magic, directable) word of deterministic finite automaton (DFA) if w sends all states of the automaton to a unique state. In 1964 Jan Cerny found a sequence of n-state complete DFA possessing a minimal synchronizing word of length (n-1)^2. He conjectured that it is an upper bound on the length of such words for complete DFA. Nevertheless, the best upper bound (n^3-n)/6 was found almost 30 years ago. We reduce the upper bound on the length of the minimal synchronizing word to n(7n^2+6n-16)/48. An implemented algorithm for finding synchronizing word with restricted upper bound is described. The work presents the distribution of all synchronizing automata of small size according to the length of an almost minimal synchronizing word.

The abstract of this article has been published in the "Intellectual Archive Bulletin" , March 2012, ISSN 1929-1329.

The Library and Archives Canada reference page: collectionscanada.gc.ca/ourl/res.php?url_ver=Z39.88......

To read the article posted on Intellectual Archive web site please click the link below.


© 2011-2017 Shiny World Corp. All rights reserved. To reach us please send an e-mail to support@IntellectualArchive.com