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
