Patterns in words and languages

Abstract

A word p, over the alphabet of variables E, is a pattern of a word w over A if there exists a non-erasing morphism h 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 word v, 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 poset of v. The 5rst part of the paper is devoted to investigate the relationships between the structure of the poset P(v) an d the combinatorial properties of the word v. Inthe last section, for a givenlan guage L, we consider the language P(L) of all patterns of words in L. The mainresult of this sectionshows that, if L is a regular language, then P(L) is a regular language too