Word reconstruction using queries on subwords or factors

Matthieu Rosenfeld
LIRMM, Montpellier
https://www.lirmm.fr/~mrosenfeld/

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 $W$ and your goal is to reconstruct $W$ by asking the least possible number of queries. We study the question for 3 different families of queries: – “How many occurrences of $u$ in $W$ as a factor?”, for any $u$; – “How many occurrences of $u$in $W$ as a subword?”, for any $u$; – “Does $u$ occur in $W$ as a subword?”, for any $u$.

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 $W$ of length $n$ in at most $n/2+1$ queries. We prove that $O\left(\right(nlogn{)}^{\left(1/2\right)})$ 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

• Combinatorics on Words Seminar
• Virtual event