Lachish, Oded and Newman, Ilan. (2011) Testing periodicity. Algorithmica, Vol.60 (No.2). pp. 401-420. ISSN 0178-4617

Full text not available from this repository.

Abstract

We study the string-property of being periodic and having periodicity smaller than a given bound. Let I pound be a fixed alphabet and let p,n be integers such that P <= n/2 . A length-n string over I pound, alpha=(alpha (1),aEuro broken vertical bar,alpha (n) ), has the property Period(p) if for every i,ja{1,aEuro broken vertical bar,n}, alpha (i) =alpha (j) whenever ia parts per thousand j (mod p). For an integer parameter the property Period(a parts per thousand currency signg) is the property of all strings that are in Period(p) for some pa parts per thousand currency signg. The property is also called Periodicity. An epsilon-test for a property P of length-n strings is a randomized algorithm that for an input alpha distinguishes between the case that alpha is in P and the case where one needs to change at least an epsilon-fraction of the letters of alpha to get a string in P. The query complexity of the epsilon-test is the number of letter queries it makes for the worst case input string of length n. We study the query complexity of epsilon-tests for Period(a parts per thousand currency signg) as a function of the parameter g, when g varies from 1 to , while ignoring the exact dependence on the proximity parameter epsilon. We show that there exists an exponential phase transition in the query complexity around g=log n. That is, for every delta > 0 and ga parts per thousand yen(log n)(1+delta) , every two-sided error, adaptive epsilon-test for Period(a parts per thousand currency signg) has a query complexity that is polynomial in g. On the other hand, for , there exists a one-sided error, non-adaptive epsilon-test for Period(a parts per thousand currency signg), whose query complexity is poly-logarithmic in g. We also prove that the asymptotic query complexity of one-sided error non-adaptive epsilon-tests for Periodicity is , ignoring the dependence on epsilon.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Algorithmica
Publisher:	Springer Verlag
ISSN:	0178-4617
Date:	June 2011
Volume:	Vol.60
Number:	No.2
Page Range:	pp. 401-420
Identification Number:	10.1007/s00453-009-9351-y
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Israel Science Foundation
Grant number:	Israel Science Foundation (1011/06)
URI:	http://wrap.warwick.ac.uk/id/eprint/41419

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item