Counting ordered patterns in words generated by morphisms

Patrice Séébold 1, 2, * Sergey Kitaev 3 Toufik Mansour 4
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Springer-Verlag. LATA'2008: 2nd International Conference on Language and Automata Theory and Applications, Mar 2008, Tarragona, Spain. LNCS (5196), pp.287-298, 2008, 〈http://grammars.grlmc.com/lata2008/〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00408114
Contributeur : Patrice Séébold <>
Soumis le : mercredi 29 juillet 2009 - 00:03:03
Dernière modification le : jeudi 11 janvier 2018 - 06:26:07
Document(s) archivé(s) le : mardi 15 juin 2010 - 19:00:16

Fichier

PatternMorph_LATA_LNCS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00408114, version 1

Collections

Citation

Patrice Séébold, Sergey Kitaev, Toufik Mansour. Counting ordered patterns in words generated by morphisms. Springer-Verlag. LATA'2008: 2nd International Conference on Language and Automata Theory and Applications, Mar 2008, Tarragona, Spain. LNCS (5196), pp.287-298, 2008, 〈http://grammars.grlmc.com/lata2008/〉. 〈lirmm-00408114〉

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

87