Skip to Main content Skip to Navigation
Conference papers

Counting ordered patterns in words generated by morphisms

Patrice Séébold 1, 2, * Sergey Kitaev 3 Toufik Mansour 4
* Corresponding author
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00408114
Contributor : Patrice Séébold <>
Submitted on : Wednesday, July 29, 2009 - 12:03:03 AM
Last modification on : Friday, June 11, 2021 - 3:34:05 AM
Long-term archiving on: : Tuesday, June 15, 2010 - 7:00:16 PM

File

PatternMorph_LATA_LNCS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00408114, version 1

Citation

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⟩

Share

Metrics

Record views

215

Files downloads

245