Word reconstruction using queries on subwords or factors

Matthieu Rosenfeld
LIRMM, Montpellier

Date(s) : 05/12/2023   iCal
15 h 00 min - 16 h 00 min

I will present some results that we recently obtained about word reconstruction problems. In this setting you can ask queries from a fixed family of queries about an unknown word and your goal is to reconstruct by asking the least possible number of queries. We study the question for 3 different families of queries: – “How many occurrences of in as a factor?”, for any ; – “How many occurrences of in as a subword?”, for any ; – “Does occur in as a subword?”, for any .

Each of these cases had already been studied, and we improve the bounds for each of them. In particular, in the second case, you can ask queries about the number of occurrences of any given subword. Fleischmann, Lejeune, Manea, Nowotka and Rigo gave an algorithm that reconstructs any binary word of length in at most queries. We prove that queries suffice. In this talk, I will provide a few necessary definitions and present our results.

This is joint work with Gwenaël Richomme.



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/

Virtual event


Retour en haut 

Secured By miniOrange