Natalie Behague
University of Victoria, Canada
https://nb453.user.srcf.net/
Date(s) : 24/10/2022 iCal
15 h 00 min - 16 h 00 min
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. Černý’s conjecture on the length of the shortest such word is one of the most famous open problem in automata theory. We considered the closely related question of determining the minimum length of a word that maps some k states onto a single state.
For synchronizing automata, we found a simple argument for general k almost halving the upper bound on the minimum length of a word sending k states to a single state. We further improved the upper bound on the minimum length of a word sending 4 states to a singleton from
to , and the minimum length sending 5 states to a singleton from to . I will discuss this result and some open questions.
This talk is based on joint work with Robert Johnson.
The address of the Zoom meeting is https://zoom.us/j/92245493528 . The password is distributed in announcements. If you want to receive them, or receive them and want to unsubscribe, please write to Anna Frid.
More info: https://www.i2m.univ-amu.fr/wiki/Combinatorics-on-Words-seminar/
Emplacement
Virtual event
Catégories