Counting ordered patterns in words generated by morphisms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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⟩
92 View
173 Download

Share

More