Localisation

Adresses

Aix-Marseille Université
Institut de Mathématiques de Marseille (I2M) - UMR 7373
Site Saint-Charles : 3 place Victor Hugo, Case 19, 13331 Marseille Cedex 3
Site Luminy : Campus de Luminy - Case 907 - 13288 Marseille Cedex 9

Word reconstruction using queries on subwords or factors




Date(s) : 05/12/2023   iCal
15h00 - 16h00

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/

Emplacement
Virtual event

Catégories Pas de Catégories


Leave a comment

Secured By miniOrange