Minimal Forbidden Words and Applications

Gabriele Fici - Universita' di Palermo
Date and time
Monday, December 9, 2013 at 5:00 PM - 4:45 p.m. rinfresco; 5:00 p.m. inizio seminario
Ca' Vignal - Piramide, Floor 0, Hall Verde
Programme Director
Zsuzsanna Liptak
External reference
Publication date
November 26, 2013
Computer Science  


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.


© 2002 - 2021  Verona University
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234