Catalog Home Page

Approximate periods of strings

Sim, J.S., Iliopoulos, C.S., Park, K. and Smyth, W.F. (2001) Approximate periods of strings. Theoretical Computer Science, 262 (1-2). pp. 557-568.

[img]
Preview
PDF - Authors' Version
Download (271kB)
Link to Published Version: http://dx.doi.org/10.1016/S0304-3975(00)00365-0
*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 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.

Publication Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2001 Elsevier Science B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27573
Item Control Page Item Control Page

Downloads

Downloads per month over past year