Cerny-Starke conjecture from the sixties of XX century

2020/03/13 by Trahtman, A. N. · 1 citation
#Discrete Mathematics (Primary) Formal Languages and Automata Theory (Secondary) #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #I.2.7

paper · doi:10.48550/arxiv.2003.06177

Abstract

A word s of letters on edges of underlying graph Γ of deterministic finite automaton (DFA) is called synchronizing if s sends all states of the automaton to a unique state. J. Černy discovered in 1964 a sequence of n-state complete DFA possessing a minimal synchronizing word of length (n-1)². The hypothesis, mostly known today as Černy conjecture, claims that (n-1)² is a precise upper bound on the length of such a word over alphabet Σ of letters on edges of Γ for every complete n-state DFA. The hypothesis was formulated in 1966 by Starke. Algebra with nonstandard operation over special class of matrices induced by words in the alphabet of labels on edges is used to prove the conjecture. The proof is based on the connection between length of words u and dimension of the space generated by solution L_x of matrix equation M_uL_x=M_s for synchronizing word s, as well as on relation between ranks of M_u and L_x. Important role below placed the notion of pseudo inverseL matrix, sometimes reversible.

Cited by

• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata

Related

• The Černy conjecture
• The length of a minimal synchronizing word and the Černy conjecture
• Row monomial matrices and Černy conjecture, short proof
• The vCerny Conjecture for aperiodic automata
• Modifying the upper bound on the length of minimal synchronizing word