6533b82cfe1ef96bd128eab8
RESEARCH PRODUCT
Patterns in words and languages
Antonio RestivoGiusi CastiglioneS. Salemisubject
PatternApplied MathematicsPartial order on wordStructure (category theory)Set (abstract data type)CombinatoricsFormal languagesSection (category theory)MorphismRegular languagePartial order on wordsDiscrete Mathematics and CombinatoricsOrder (group theory)Partially ordered setWord (group theory)Mathematicsdescription
AbstractA 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, given two words u,v∈A∗, we write u⩽v if u is a pattern of v. The restriction of ⩽ 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 u⩽v. P(v), with the relation ⩽, is a poset and it is called the pattern poset of v. The first part of the paper is devoted to investigate the relationships between the structure of the poset P(v) and the combinatorial properties of the word v. In the last section, for a given language L, we consider the language P(L) of all patterns of words in L. The main result of this section shows that, if L is a regular language, then P(L) is a regular language too.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2004-12-01 | Discrete Applied Mathematics |