Combinatorics of periods in strings

Rivals, Eric; Rahmann, Sven

doi:10.1016/S0097-3165(03)00123-7

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Combinatorics of periods in strings

MPS-Authors

/persons/resource/persons50480

Rahmann, Sven
Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Rivals, E., & Rahmann, S. (2003). Combinatorics of periods in strings. Journal of Combinatorial Theory Series A, 104(1), 95-113. doi:10.1016/S0097-3165(03)00123-7.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0010-899A-D

Abstract

We consider the set Γn of all period sets of strings of length n over a finite alphabet. We show that there is redundancy in period sets and introduce the notion of an irreducible period set. We prove that Γn is a lattice under set inclusion and does not satisfy the Jordan–Dedekind condition. We propose the first efficient enumeration algorithm for Γn and improve upon the previously known asymptotic lower bounds on the cardinality of Γn. Finally, we provide a new recurrence to compute the number of strings sharing a given period set, and exhibit an algorithm to sample uniformly period sets through irreducible period set.