PATTERN LANGUAGES WITH AND WITHOUT ERASING

The paper deals with the problems related to finding a pattern common to all words in a given set. We restrict our attention to patterns exp ressible by the use of variables ranging over words. Two essentially d ifferent cases result, depending on whether or not the empty word belo ngs to the range. We investigate equivalence and inclusion problems, p atterns descriptive for a set, as well as some complexity issues. The inclusion problem between two pattern languages turns out to be of fun damental theoretical importance because many problems in the classical combinatorics of words can be reduced to it.