November 24, Wednesday 14:15, Room 303, Jacobs Building

Title: Combinatorics on Compressed Suffix Arrays

Lecturer : Roberto Grossi

Lecturer homepage : http://www.di.unipi.it/~grossi/

Affiliation : Department of Information, University of Pisa

Suffix arrays are a key data structure for solving a run of problems on texts and sequences. Over the years, many interesting combinatorial properties have been devised for the special class of permutations arising from suffix arrays: they can implicitly encode extra information, they are a well characterized subset of the n! permutations, and so on. We explore and review some of their algorithmic features, discussing the space issues related to their usage in text indexing, combinatorial pattern matching, and data compression.