Testing of matrix-poset properties (Q2460630)

The paper refers to labeled \(d\)-dimensional grids, the grid being viewed as partially ordered sets (posets). The main result represents an (\(\epsilon\), poly\((1/ \epsilon)\))-test for every property \(0/1\) labeled, \(d\)-dimensional grids characterized by a finite collection of forbidden induced posets. The class of properties is related to properties defined by first ordered formulae with no quantifier alternation over the syntax containing the grid order relations. The authors also show that that with one quantifier alteration, a propertie for which no tests of query complexity of \(O(n^{1/4})\) exists. The results identify new classes of properties defined by means of restricted logics and efficiently testable.