Counting ordered patterns in words generated by morphisms

Sergey Kitaev, Toufik Mansour, Patrice Seebold

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

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.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publicationSecond International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers
EditorsCarlos Martín-Vide , Friedrich Otto, Henning Fernau
Place of PublicationBerlin
PublisherSpringer
Pages287-298
Number of pages12
ISBN (Print)9783540882817
DOIs
Publication statusPublished - 2008
Event2nd International Conference on Language and Automata Theory and Applications (LATA) - Tarragona, Spain
Duration: 13 Mar 200819 Mar 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5196
ISSN (Print)0302-9743

Conference

Conference2nd International Conference on Language and Automata Theory and Applications (LATA)
CountrySpain
CityTarragona
Period13/03/0819/03/08

Keywords

  • morphisms
  • patterns
  • rises
  • inversions
  • repititions

Cite this

Kitaev, S., Mansour, T., & Seebold, P. (2008). Counting ordered patterns in words generated by morphisms. In C. Martín-Vide , F. Otto, & H. Fernau (Eds.), Language and Automata Theory and Applications: Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers (pp. 287-298). (Lecture Notes in Computer Science; Vol. 5196). Springer. https://doi.org/10.1007/978-3-540-88282-4_27