DIMACS - Graduate Student Combinatorics Seminar

Title: On Synchronizing Automata

Speaker: Brian Nakamura, Rutgers University

Date: Wednesday, April 18, 2012 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


A deterministic finite automaton is called synchronizing if there exists a "reset" word that sends every state to one particular state. A number of questions have been asked about this class of automaton. In this talk, I will discuss some of those questions including an open problem known as the Cerny Conjecture. No prior background (in this area) will be assumed.

Graduate Student Combinatorics Seminars