Patterns in words and languages

Research output: Contribution to journalArticle

4 Citations (Scopus)

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 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
Original languageEnglish
Pages (from-to)237-246
Number of pages10
JournalDiscrete Applied Mathematics
Volume144
Publication statusPublished - 2004

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this