Minimal Forbidden Words and Applications

Relatore
Gabriele Fici - Universita' di Palermo
Data e ora
lunedì 9 dicembre 2013 alle ore 17.00 - 4:45 p.m. rinfresco; 5:00 p.m. inizio seminario
Luogo
Ca' Vignal - Piramide, Piano 0, Sala Verde
Referente
Zsuzsanna Liptak
Referente esterno
Data pubblicazione
26 novembre 2013
Dipartimento
Informatica  

Riassunto

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  Università degli studi di Verona
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234