Minimal Forbidden Words and Applications

Relatore:  Gabriele Fici - Universita' di Palermo
  lunedì 9 dicembre 2013 alle ore 17.00 4:45 p.m. rinfresco; 5:00 p.m. inizio seminario
A minimal forbidden word for a language L is a word that does not belong to L but all of its proper factors do. The set of minimal forbidden words has proved to be a powerful tool to investigate the combinatorial structure of a language. Actually, minimal forbidden words have been introduced in several fields of Computer Science with different names. For example, the notion of minimal forbidden word is equivalent to that of "first offender" in Symbolic Dynamics, "antidictionary" in Data Compression, or "minimal absent word" in Bioinformatics. We briefly survey the general theory of minimal forbidden words and show some algorithmic applications.


Titolo Formato  (Lingua, Dimensione, Data pubblicazione)
slides  pdfpdf (it, 227 KB, 10/12/13)

Ca' Vignal - Piramide, Piano 0, Sala Verde

Zsuzsanna Liptak

Referente esterno
Data pubblicazione
26 novembre 2013

Offerta formativa