Un DFA tiene una palabra de sincronización si hay una cadena que envía cualquier estado del DFA a un solo estado. En 'La conjetura de Cerny para autómatas aperiódicos ”por AN Trahtman (Matemática discreta y ciencias de la computación teórica vol. 9: 2, 2007, pp.3-10), escribió: Cerny conjeturó...
Un autómata determinista se llama -local para si para cada el conjunto contiene como máximo un elemento. Intuitivamente, eso significa que si una palabra de longitud conduce a un estado, entonces este estado es único, o dicho de manera diferente de una palabra arbitraria de longitud los últimos...
La conjetura de Cerny es la afirmación de que cualquier autómata de sincronización con nnn estados tiene una palabra de longitud de sincronización como máximo (n−1)2(n−1)2(n-1)^2 . El mejor límite superior actual para la longitud de una palabra de sincronización es O(n3)O(n3)O(n^3) . Digamos que...