Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

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 Item Control Page

Downloads

Downloads per month over past year