Seminar: Synchronizing Times for k-sets in Automata
- Date
- September 29, 2020
- Time
- 2:00 PM EDT - 3:00 PM EDT
- Location
- Virtually via Zoom (Registration required - Contact an organizer)
- Open To
- All faculty, staff, students and guests are welcome to attend.
- Contact
- Michelle Delcourt (mdelcourt@torontomu.ca), Melissa Huggan (melissa.huggan@torontomu.ca), Trent Marbach (trent.marbach@torontomu.ca)
An automaton consists of a finite set of states and a collection of functions from the set of states to itself. An automaton is synchronizing if there is a word (that is, a sequence of functions) that maps all states onto the same state. Cerny’s conjecture on the length of the shortest such word is probably the most famous open problem in automata theory. We consider the closely related question of determining the minimum length of a word that maps k states onto a single state.
We have improved the upper bound on the minimum length of a word that sends some triple to a single state from 0.5n2 to roughly 0.19n2. I will discuss this result and some related results, including a generalisation from triples to 4-sets and 5-sets.
This is joint work with Robert Johnson.