Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Tiling Periodicity
verfasst von : Juhani Karhumäki, Yury Lifshits, Wojciech Rytter
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We contribute to combinatorics and algorithmics of words by introducing new types of periodicities in words. A
tiling period
of a word
w
is partial word
u
such that
w
can be decomposed into several disjoint parallel copies of
u
, e.g.
a
⋄
b
is a tiling period of
aabb
. We investigate properties of tiling periodicities and design an algorithm working in
O
(
n
log(
n
)loglog(
n
)) time which finds a tiling period of minimal size, the number of such periods and their compact representation. The combinatorics of tiling periods differs significantly from that for classical full periods, for example unlike the classical case the same word can have many different primitive tiling periods. We consider also a related new type of periods called in the paper
multi-periods
. As a side product of the paper we solve an open problem posted by T. Harju.