Evènement pour le groupe Séminaire du LaBRI

Date 2008-03-06  14:00-15:00
TitreSé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."  
LieuAmphi LaBRI 
OrateurMarkus Lohrey 
UrlUniversité de Leipzig 

Aucun document lié à cet événement.

Retour à l'index