Testing for Forbidden Order Patterns in an Array

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f: {1, …, n} → ℝ of length n contains a pattern is the group of permutations of k elements), iff there are indices i 1 < i 2 < · · · < i k, such that f (i x ) > f (i y ) whenever π(χ) > π( y ). If f does not contain π, we say f is π-free. For example, for π = (2, 1), the property of being π-free is equivalent to being non-decreasing, i. e. monotone. The property of being ( k, k — 1, …, 1)-free is equivalent to the property of having a partition into at most k - 1 non-decreasing subsequences. Let k constant, be a (forbidde n ) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that f is π-free from the case that f differs in more than en places from any π-free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i. e. , ( k, k - 1, …, 1) and (1, 2, …, k ), we design non-adaptive one-sided error ε-tests of (∊ −1 log n ) O ( k 2 ) query complexity. For non-monotone patterns, we show that for any size- k non-monotone π, any non-adaptive one-sided error ε-test requires at least Ω(γ / η) queries. This general lower bound can be further strengthened for specific non-monotone k -length patterns to Ω( n 1–2/( k +1) ). On the other hand, there always exists a non- adaptive one-sided error ε-test for with O(e −1/k n 1–1/k ) query complexity Again, this general upper bound can be further strengthened for specific non-monotone patterns. E. g. , for π = (1, 3, 2), we describe an ε-test with (almost tight) query complexity of Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any tests π-freeness by making (∊ −1 logn) O(1) queries. For all algorithms presented here, the running times are linear in their query complexity.

Authors

• Ilan Newman
• Yuri Rabinovich
• Deepak Rajendraprasad
• Christian Sohler

Keywords

No keywords are indexed for this paper.