Approximate Periods of Strings

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

doi:10.1007/3-540-48452-3_10

Back

Journal article

Peer reviewed

Approximate Periods of Strings

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

Combinatorial Pattern Matching, Vol.1645, pp.123-133

1999

DOI: https://doi.org/10.1007/3-540-48452-3_10

Files and links (1)

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 rules.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
K. Park (Author/Creator) - Seoul National University
C.S. Iliopoulos (Author/Creator) - Curtin University
W.F. Smyth (Author/Creator) - Curtin University
Publication Details: Combinatorial Pattern Matching, Vol.1645, pp.123-133
Publisher: Springer Verlag
Identifiers: 991005543742407891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article
Note: Book title: Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99 Warwick University, UK, July 22–24, 1999 Proceedings

Metrics

30 Record Views