Patterns in words and languages

A word p, over the alphabet of variables E, is a pattern of a word w over A if there exists a non-erasing morphismh from E. to A. such that h(p) = w. If we take E = A, giventwo words u; v ¡ô A., we write u6v if u is a patternof v.The restrictionof 6 to aA., where A is the binary alphabet {a; b}, is a partial order relation. We introduce, given a wordv, the set P(v) of all words u such that u6v. P(v), with the relation 6, is a poset and it is called the pattern posetof v. The 5rst part of the paper is devoted to investigate the relationships between the structure of the poset P(v) an dthe combinatorial properties of the word v. Inthe last section, for a givenlan guage L, we consider the language P(L) ofall patterns of words in L. The mainresult of this sectionshows that, if L is a regular language, then P(L) is a regularlanguage too