|
Evènement pour le groupe Séminaire du LaBRI
Date | 2008-03-06 14:00-15:00 |
Titre | Séminaire LaBRI, Markus Lohrey, Algorithmics on compressed strings |
Résumé | Markus Lohrey (Université de Leipzig) est un invité au LaBRI de Géraud Senizergue.
Son exposé s'intitule
Algorithmics on compressed strings
(joint work with Yury Lifshits and Saul Schleimer).
En voici le résumé :
"In recent years, straight-line programs (SLPs) turned out to be
a convenient formalism for investigating algorithms on
compressed string data. An SLP is a context-free
grammar that generates exactly one string $w$. Since the
length of the generated string $w$ may grow exponentially with
the size of the SLP, the latter may be seen as
a compressed representation of $w$. The output of many
practical compression algorithms, like for instance those of the Lempel-Ziv
family, can be considered as SLPs. The talk will
give an overview on recent complexity results for
algorithmic string problems, where the input string is given
compressed as an SLP. Also applications in other fields
like for instance algorithmic groups theory will be presented.
If time permits, extensions to compressed trees will be
discussed."
|
Lieu | Amphi LaBRI |
Orateur | Markus Lohrey |
Url | Université de Leipzig |
Aucun document lié à cet événement. RetourRetour à l'index
| |