Approximate periods of strings

J.S. Sim; C.S. Iliopoulos; K. Park; W.F. Smyth

doi:10.1016/S0304-3975(00)00365-0

Back

Journal article

Open access

Peer reviewed

Approximate periods of strings

J.S. Sim, C.S. Iliopoulos, K. Park and W.F. Smyth

Theoretical Computer Science, Vol.262(1-2), pp.557-568

2001

DOI: https://doi.org/10.1016/S0304-3975(00)00365-0

Files and links (2)

pdf

sips-1.pdfDownload View

Author’s Version Open Access

url

Link to Published Version *Subscription may be requiredView

Abstract

The study of approximately periodic strings is relevant to diverse applications such as molecular biology, data compression, and computer-assisted music analysis. Here we study different forms of approximate periodicity under a variety of distance functions. We consider three related problems, for two of which we derive polynomial-time algorithms; we then show that the third problem is NP-complete.

Details

Title: Approximate periods of strings
Authors/Creators: J.S. Sim (Author/Creator) - Seoul National University
C.S. Iliopoulos (Author/Creator) - King's College London
K. Park (Author/Creator) - Seoul National University
W.F. Smyth (Author/Creator) - McMaster University
Publication Details: Theoretical Computer Science, Vol.262(1-2), pp.557-568
Publisher: Elsevier BV
Identifiers: 991005544462307891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

136 File views/ downloads

114 Record Views

23 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1103 Efficient Algorithms
Web Of Science research areas: Computer Science, Theory & Methods
ESI research areas: Computer Science