# On Černy's conjecture

Seminar

Speaker

Avraham Trakhtman (Bar-Ilan University)

Date

11/01/2023 - 11:30 - 10:30Add to Calendar

`2023-01-11 10:30:00``2023-01-11 11:30:00``On Černy's conjecture``A word w of letters on edges of the underlying graph of a deterministic finite automaton (DFA) is called synchronizing if w 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)^2. The hypothesis, well known today as the Černy conjecture, formulated in 1966 by Starke, claims that the precise upper bound on the length of a synchronizing word for a complete DFA is (n-1)^2. An effort to prove the Černy conjecture is presented in PowerPoint on flash drive. ===================================== https://us02web.zoom.us/j/87856132062 Meeting ID: 878 5613 2062``Third floor seminar room and Zoom``אוניברסיטת בר-אילן - Department of Mathematics``mathoffice@math.biu.ac.il``Asia/Jerusalem``public`Place

Third floor seminar room and Zoom

Abstract

A word w of letters on edges of the underlying graph of a deterministic

finite automaton (DFA) is called synchronizing if w 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)^2.

The hypothesis, well known today as the Černy conjecture, formulated in 1966 by Starke, claims that the precise upper bound on the length of a synchronizing word for a complete DFA is (n-1)^2. An effort to prove the Černy conjecture is presented in PowerPoint on flash drive.

=====================================

https://us02web.zoom.us/j/87856132062

Meeting ID: 878 5613 2062

Last Updated Date : 21/12/2022