caa a22 4500 445804629 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9351-y doi (NATIONALLICENCE)springer-10.1007/s00453-009-9351-y Testing Periodicity [Elektronische Daten] [Oded Lachish, Ilan Newman] We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet and let p,n be integers such that $p\leq \frac{n}{2}$ . A length-n string over Σ, α=(α 1, ,α n), has the property Period(p) if for every i,j∈{1, ,n}, α i=α j whenever i≡j (mod p). For an integer parameter $g\leq \frac{n}{2},$ the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property $\mathit{Period}(\leq \frac{n}{2})$ is also called Periodicity. An ε-test for a property P of length-n strings is a randomized algorithm that for an input α distinguishes between the case that α is in P and the case where one needs to change at least an ε-fraction of the letters of α to get a string in P. The query complexity of the ε-test is the number of letter queries it makes for the worst case input string of length n. We study the query complexity of ε-tests for Period(≤g) as a function of the parameter g, when g varies from 1 to $\frac{n}{2}$ , while ignoring the exact dependence on the proximity parameter ε. We show that there exists an exponential phase transition in the query complexity around g=log n. That is, for every δ>0 and g≥(log n)1+δ , every two-sided error, adaptive ε-test for Period(≤g) has a query complexity that is polynomial in g. On the other hand, for $g\leq \frac{\log{n}}{6}$ , there exists a one-sided error, non-adaptive ε-test for Period(≤g), whose query complexity is poly-logarithmic ing. We also prove that the asymptotic query complexity of one-sided error non-adaptive ε-tests for Periodicity is $\Theta(\sqrt{n\log n}\,)$ , ignoring the dependence on ε. Springer Science+Business Media, LLC, 2009 Property testing nationallicence Periodicity nationallicence Lachish Oded Department of Computer Science, University of Warwick, CV4 7AL, Coventry, UK aut Newman Ilan Department of Computer Science, University of Haifa, 31905, Haifa, Israel aut Algorithmica Springer-Verlag 60/2(2011-06-01), 401-420 0178-4617 60:2<401 2011 60 453 https://doi.org/10.1007/s00453-009-9351-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9351-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Lachish Oded Department of Computer Science, University of Warwick, CV4 7AL, Coventry, UK aut NATIONALLICENCE 700 1- Newman Ilan Department of Computer Science, University of Haifa, 31905, Haifa, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 401-420 0178-4617 60:2<401 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer