Patterns in words and languages

Risultato della ricerca: Article

4 Citazioni (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
Lingua originaleEnglish
pagine (da-a)237-246
Numero di pagine10
RivistaDiscrete Applied Mathematics
Volume144
Stato di pubblicazionePublished - 2004

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cita questo