Minimal Forbidden Words in Formal Languages and Applications

Gabriele Fici ( University of Palermo )

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.