Kolloquiumsvortrag Marie Lejeune, Universität Liège, Belgien / am 19.06.2020

19.06.2020 von 14:15 bis 15:45

Ludewig-Meyn-Str. 2, Semiarraum Ü2/K

Titel: Reconstructing Words from Right-Bounded Binary Block Words

Abstract:

A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word $w\in\{a,b\}^*$ can be reconstructed from the number of occurrences of at most $\min(|w|_a,|w|_b)+1$ scattered factors of the form $a^i b$, where $|w|_a$ is the number of occurrences of the letter $a$ in $w$. Moreover, we generalize the result to alphabets of the form $\{1, \ldots, q\}$ by showing that at most $\sum_{i=1}^{q-1} |w|_i \, (q-i+1)$ scattered factors suffices to reconstruct $w$. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here.

https://www.tf.uni-kiel.de/de/fakultaet/aktuelles/copy_of_Kolloquium-sose-2020/kolloquium-informatik

Prof. Dr. Dirk Nowotka

Diesen Termin meinem iCal-Kalender hinzufügen

zurück