The separating words, k-deck, and trace reconstruction problems
Zachary Chase
University of Oxford
http://people.maths.ox.ac.uk/~chase/
Date(s) : 11/07/2022 iCal
15h00 - 16h00
What is the smallest size of a DFA that can separate two given strings of length ? Can two distinct strings of length have the same multiset of subsequences of length ? How many random subsequences of length of an unknown string of length do you need to determine with high probability? We discuss these three problems, each having an exponential gap between the best known upper and lower bounds, and touch upon how they might be more related than one might expect.
Video and slides here : https://www.i2m.univ-amu.fr/wiki/Combinatorics-on-Words-seminar/
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.
Catégories Pas de Catégories
