============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

                  Tarde de Combinatória
============================================================

Título:      On the number of prefix and border tables
            
Palestrante: Laura Giambruno
             Université de Caen

Hora e Data: 14h, sexta-feira, 28 de março de 2014

Local:       Sala Multi-usos do Numec

Resumo:

The   prefix   table   of   a  string w reports   for   each
position i the  length of  the  longest substring  of w that
begins at i and matches a prefix of w. This table stores the
same information  as the border  table of the  string, which
memorizes for  each position the maximal  length of prefixes
of the string w ending  at that position. Indeed two strings
have the same border table if and only if they have the same
prefix table.

Both   tables   are   useful   in  several   algorithms   on
strings. They  are used to design  efficient string matching
algorithms   and   are    essential   for   this   type   of
applications.  It   has  been  noted  that   for  some  text
algorithms  (like  the  Knuth-Morris-Pratt pattern  matching
algorithm), the  string itself is not  considered but rather
its structure meaning that  two strings with the same prefix
or border table are treated in the same manner. The study of
these tables has  become topical and it has  been subject of
recent interest by several authors.    In this talk we focus
on  the problem  of enumerating  distinct prefix  and border
tables of  a given length.  For this purpose, we  define the
combinatorial class  of p-lists, where a p-list  is a finite
sequence of non-negative  integers. We constructively define
an injection  from the  set of prefix  tables to the  set of
p-lists  which are  easier to  count. We  then deduce  a new
upper bound  and a new lower  bound on the  number of prefix
tables  for strings  of length  n or,  equivalently,  on the
number of border tables of length n.

Joint work together with Julien Clément of University of Caen.