Catalog Home Page

Approximate Periods of Strings

Sim, J.S., Park, K., Iliopoulos, C.S. and Smyth, W.F. (1999) Approximate Periods of Strings. Lecture Notes in Computer Science, 1645 . pp. 123-133.

Link to Published Version: http://dx.doi.org/10.1007/3-540-48452-3_10
*Subscription may be required

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.

Publication Type: Journal Article
Publisher: Springer Verlag
Copyright: 1999 Springer-Verlag
Notes: Book title: Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99 Warwick University, UK, July 22–24, 1999 Proceedings
URI: http://researchrepository.murdoch.edu.au/id/eprint/27563
Item Control Page Item Control Page