BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:4988@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20231205T150000
DTEND;TZID=Europe/Paris:20231205T160000
DTSTAMP:20240524T072506Z
URL:https://www.i2m.univ-amu.fr/evenements/word-reconstruction-using-queri
 es-on-subwords-or-factors/
SUMMARY: (...): Word reconstruction using queries on subwords or factors
DESCRIPTION:: I will present some results that we recently obtained about w
 ord reconstruction problems. In this setting you can ask queries from a fi
 xed family of queries about an unknown word W and your goal is to reconstr
 uct W by asking the least possible number of queries. We study the questio
 n for 3 different families of queries: - “How many occurrences of u in W
  as a factor?”\, for any u\; - “How many occurrences of uin W as a sub
 word?”\, for any u\; - “Does u occur in W as a subword?”\, for any u
 .\nEach of these cases had already been studied\, and we improve the bound
 s for each of them. In particular\, in the second case\, you can ask queri
 es about the number of occurrences of any given subword. Fleischmann\, Lej
 eune\, Manea\, Nowotka and Rigo gave an algorithm that reconstructs any bi
 nary word W of length n in at most n/2+1 queries. We prove that O((nlogn)(
 1/2)) queries suffice. In this talk\, I will provide a few necessary defin
 itions and present our results.\nThis is joint work with Gwenaël Richomme
 .\n.\n&nbsp\;\n\n\n\nThe 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.\nMore info: https://www.i2m.univ-amu.fr/wiki/Combinatorics-on-W
 ords-seminar/
CATEGORIES:Combinatorics on Words Seminar,Virtual event
LOCATION:Virtual event\, visioconférence\, virtual\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=visioconférence\, virtual\
 , France;X-APPLE-RADIUS=100;X-TITLE=Virtual event:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20231029T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR