Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Combinatorics of Periods in Strings
| |
|
Combinatorics of Periods in Strings
Eric Rivals7 and Sven Rahmann8 
| (7) |
L.I.R.M.M., CNRS U.M.R. 5506, 161 rue Ada, F-34392 Montpellier Cedex 5, France |
| (8) |
Dept. of Computational Molecular Biology, Max-Planck-Institut für Molekulare Genetik, Ihnestraße 73, D-14195 Berlin, Germany |
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 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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|