Patterns in words and languages

Risultato della ricerca: Articlepeer review

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

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Entra nei temi di ricerca di 'Patterns in words and languages'. Insieme formano una fingerprint unica.

Cita questo