Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: An overview of the Cernư Conjecture
Speaker: Brian Nakamura, Rutgers University
Date: Thursday, November 10, 2011 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
A deterministic finite automaton is called synchronizing if there exists a word that sends every state to one particular state. Any such word with this property is called a synchronizing word. The Cernư Conjecture, which has been open since 1964, states that any n-state synchronizing automaton must have a synchronizing word of length at most (n-1)^2. In this expository talk, we will outline some of the classical and more recent results toward settling this conjecture.