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.

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.

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

Item Control Page

Downloads