Counting ordered patterns in words generated by morphisms

Sergey Kitaev; Toufik Mansour; Patrice Seebold

doi:10.1007/978-3-540-88282-4_27

Counting ordered patterns in words generated by morphisms

Sergey Kitaev, Toufik Mansour, Patrice Seebold

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Language and Automata Theory and Applications
Subtitle of host publication	Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers
Editors	Carlos Martín-Vide , Friedrich Otto, Henning Fernau
Place of Publication	Berlin
Publisher	Springer
Pages	287-298
Number of pages	12
ISBN (Print)	9783540882817
DOIs	https://doi.org/10.1007/978-3-540-88282-4_27
Publication status	Published - 2008
Event	2nd International Conference on Language and Automata Theory and Applications (LATA) - Tarragona, Spain Duration: 13 Mar 2008 → 19 Mar 2008

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5196
ISSN (Print)	0302-9743

Conference

Conference	2nd International Conference on Language and Automata Theory and Applications (LATA)
Country	Spain
City	Tarragona
Period	13/03/08 → 19/03/08

Keywords

morphisms
patterns
rises
inversions
repititions

Access to Document

10.1007/978-3-540-88282-4_27

http://link.springer.com/book/10.1007/978-3-540-88282-4

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

Kitaev, Sergey ; Mansour, Toufik ; Seebold, Patrice. / Counting ordered patterns in words generated by morphisms. Language and Automata Theory and Applications: Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers. editor / Carlos Martín-Vide ; Friedrich Otto ; Henning Fernau. Berlin : Springer, 2008. pp. 287-298 (Lecture Notes in Computer Science).

@inproceedings{4dbbeb2b1d8f4be8a308cd40c573d188,

title = "Counting ordered patterns in words generated by morphisms",

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.",

keywords = "morphisms, patterns, rises, inversions, repititions",

author = "Sergey Kitaev and Toufik Mansour and Patrice Seebold",

year = "2008",

doi = "10.1007/978-3-540-88282-4_27",

language = "English",

isbn = "9783540882817",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "287--298",

editor = "{Mart{\'i}n-Vide }, Carlos and Friedrich Otto and Henning Fernau",

booktitle = "Language and Automata Theory and Applications",

note = "2nd International Conference on Language and Automata Theory and Applications (LATA) ; Conference date: 13-03-2008 Through 19-03-2008",

}

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. Lecture Notes in Computer Science, vol. 5196, Springer, Berlin, pp. 287-298, 2nd International Conference on Language and Automata Theory and Applications (LATA), Tarragona, Spain, 13/03/08. https://doi.org/10.1007/978-3-540-88282-4_27

Counting ordered patterns in words generated by morphisms. / Kitaev, Sergey; Mansour, Toufik; Seebold, Patrice.

Language and Automata Theory and Applications: Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers. ed. / Carlos Martín-Vide ; Friedrich Otto; Henning Fernau. Berlin : Springer, 2008. p. 287-298 (Lecture Notes in Computer Science; Vol. 5196).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Counting ordered patterns in words generated by morphisms

AU - Kitaev, Sergey

AU - Mansour, Toufik

AU - Seebold, Patrice

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - morphisms

KW - patterns

KW - rises

KW - inversions

KW - repititions

UR - http://link.springer.com/book/10.1007/978-3-540-88282-4

U2 - 10.1007/978-3-540-88282-4_27

DO - 10.1007/978-3-540-88282-4_27

M3 - Conference contribution book

SN - 9783540882817

T3 - Lecture Notes in Computer Science

SP - 287

EP - 298

BT - Language and Automata Theory and Applications

A2 - Martín-Vide , Carlos

A2 - Otto, Friedrich

A2 - Fernau, Henning

PB - Springer

CY - Berlin

T2 - 2nd International Conference on Language and Automata Theory and Applications (LATA)

Y2 - 13 March 2008 through 19 March 2008

ER -

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