Minimal Forbidden Words and Applications

Speaker:  Gabriele Fici - Universita' di Palermo
  Monday, December 9, 2013 at 5:00 PM 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.


Title Format  (Language, Size, Publication date)
slides  pdfpdf (it, 227 KB, 10/12/13)

Ca' Vignal - Piramide, Floor 0, Hall Verde

Programme Director
Zsuzsanna Liptak

Publication date
November 26, 2013