Counting ordered patterns in words generated by morphisms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2008

Counting ordered patterns in words generated by morphisms

Sergey Kitaev
  • Fonction : Auteur
  • PersonId : 860206
Toufik Mansour

Résumé

We start a general study of counting the number of occurrences of ordered patterns in words generated by morphisms.We consider certain patterns with gaps (classical patterns) and that with no gaps (consecutive patterns). Occurrences of the patterns are known, in the literature, as rises, descents, (non-)inversions, squares and p-repetitions. We give recurrence formulas in the general case, then deducing exact formulas for particular families of morphisms. Many (classical or new) examples are given illustrating the techniques and showing their interest.
Fichier principal
Vignette du fichier
PatternMorph_LATA_LNCS.pdf (140.31 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00408114 , version 1 (29-07-2009)

Identifiants

  • HAL Id : lirmm-00408114 , version 1

Citer

Patrice Séébold, Sergey Kitaev, Toufik Mansour. Counting ordered patterns in words generated by morphisms. LATA'2008: 2nd International Conference on Language and Automata Theory and Applications, Mar 2008, Tarragona, Spain. pp.287-298. ⟨lirmm-00408114⟩
99 Consultations
181 Téléchargements

Partager

More