Conference Papers Year : 2008

Counting ordered patterns in words generated by morphisms

Sergey Kitaev
  • Function : Author
  • PersonId : 860206
Toufik Mansour

Abstract

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
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00408114 , version 1

Cite

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⟩
102 View
189 Download

Share

More