DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Brian Nakamura, Rutgers University, bnaka {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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

Abstract:

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.

See: http://www.math.rutgers.edu/~bnaka/expmath/