Relational Properties Expressible with One
Universal Quantifier Are Testable
Charles Jordan? and Thomas Zeugmann??
Division of Computer Science
Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan{skip,thomas}@ist.hokudai.ac.jp

Abstract. In property testing a small, random sample of an object istaken and one wishes to distinguish with high probability between thecase where it has a desired property and the case where it is far from having the property. Much of the recent work has focused on graphs. In thepresent paper three generalized models for testing relational structures
are introduced and relationships between these variations are shown.
Furthermore, the logical classification problem for testability is considered and, as the main result, it is shown that Ackermann’s class withequality is testable.
Key words: property testing, logic

1

Introduction

Property testing is an application of induction. Given a large object such as agraph or database, we wish to state a conclusion about the entire object after
examining a small, randomly selected sample. Lovász [19] has described it as the“third reincarnation” of this approach, after statistics and machine learning.
Property testers are probabilistic approximation algorithms that examine
only a small part of their input. Our goal is always to distinguish inputs that havesome desired property from inputs that are far from having it. We are especiallyinterested in classification, i.e., the testability of large classes of properties.
The paper is structured as follows. In Subsection 1.1, we outline the historyof testing, focusing on results that influence our approach. Much recent work
has focused on graphs, while we seek a general framework that we call relational
property testing. Definitions and notation are in Section 2. In Section 3 we show
the relationships between variations of our framework. We use the frameworkfrom previous sections to state the classification problem for testability in Section 4, and show that Ackermann’s class with equality is testable (cf. Theorem 4)in all of the variations considered in previous sections.
?
??

Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas underGrant No. 21013001.

142

C. Jordan and T. Zeugmann

1.1

History of Property Testing

We begin with a brief history and overview of property testing. There are also a
number of surveys of property testing, see for example Fischer [12] or Ron [25].
Property testing is a form of approximation where we trade accuracy for efficiency. Probabilistic machines seem to have been first formalized by de Leeuw
et al. [18], who showed that such machines cannot compute uncomputable properties under reasonable assumptions. However, they mention the possibility thatprobabilistic machines could be more efficient than deterministic machines. An
early example of such a result is Freivalds’ [14] matrix multiplication checker.
Property testing itself began in program verification (see Blum et al. [8] andRubinfeld and Sudan [26]). Goldreich et al. [16] first considered the testability ofgraph properties and showed the existence of testable NP-complete properties.
An approach using incidence lists to represent bounded-degree graphs was introduced by Goldreich and Ron [15]. Parnas and Ron [22] generalized this approachand attempted to move away from the functional representation of structures.
For other types of structures, Alon et al. [4] showed that the regular languages
are testable and that there exist untestable context-free languages. Chockler and
Kupferman [11] extended the positive result to the ω-regular languages.
There is also recent work on testing properties of (usually uniform) hypergraphs. In particular, Fischer et al. [13] defined a general model that is roughly
equivalent to one of our models, namely Tr based on Definition 8, and showedthat hypergraph partition problems are testable in this framework. However,much of the recent work has been focused on graphs and Alon and Shapira [6]survey some of the recent results in testing graph properties.
Alon et al. [2] began a logical characterization of the testable (graph) properties, see Section 4. Alon and Shapira [5] gave a (near) characterization of anatural subclass of the testable graph properties, which Rödl and Schacht [24]generalized to hypergraphs. Alon et al. [3] showed a combinatorial characterization of the graph properties testable with a constant number of queries.

2

Preliminaries

Instead of restricting our attention to, for example, graphs, we focus on property
testing in a general setting. We begin by defining vocabularies.
Definition 1. A vocabulary τ is a tuple of distinct predicate symbols Ri together
with their arities ai ,
τ := (R1a1 , . . . , Rsas ) .
Two examples of vocabularies are τG := (E 2 ), the vocabulary of directed
graphs and τS := (S 1 ), the vocabulary of binary strings.
Definition 2. A structure A of type τ is an (s + 1)-tupleA
A := (U, RA
1 , . . . , Rs ) ,aiwhere U is a finite universe and each RA
is a predicate corresponding toi ⊆U
the predicate symbol Ri of τ .

Relational Properties Expressible with One ∀ Quantifier Are Testable

143

We identify U with the non-negative integers {0, . . . , n−1} and use n = #(A)for the size of the universe of a structure A. The universe U of a binary stringis the set of bit positions, which we will identify as {0, . . . , n − 1} from left toright. For i ∈ U , we interpret i ∈ S as “bit i of the string is 1.”n
The set of all structures of type τ and universe(τ ) and the
S size n is STRUCnset of all structures of type τ is STRUC (τ ) := 0≤n STRUC (τ ). A property oftype τ is any subset of STRUC (τ ). For A ∈ P , we say A has P . We use language
to refer to string properties, P to denote properties and P1 \P2 for set difference.
2.1

Property Testing Definitions

We wish to distinguish, with high probability, between inputs that have a desired
property and inputs that are far from having the property. We begin by defining a distance measure between structures. Changing the definition of distanceresults in a different model for relational testing. The symbol ⊕ is exclusive-or.
Definition 3. Let A, B ∈ STRUC (τ ) be any structures such that #(A) =#(B) = n. The distance between structures A and B isP
dist(A, B) :=1≤i≤s |{x | x ∈ U

ai

B
and RAi (x) ⊕ Ri (x)}|

Ps

i=1 n

ai

.

The dist distance is the fraction of assignments on which the two structures
disagree. It is equivalent to the definition that would result from mapping relational structures to binary strings and using the usual definitions for testing
strings. We now give the remaining definitions for testing, and will then givealternatives to Definition 3 (cf. Definitions 8 and 12).
Definition 4. Let P be a property of structures with vocabulary τ and let A besuch a structure with a universe of size n. Then,dist(A, P ) :=min

A0 ∈P ∩STRUC n (τ )dist(A, A0 ) .

Definition 5. An ε-tester for property P is a randomized algorithm given an
oracle which answers queries for the universe size and truth values of relations
on desired tuples in a structure A. The tester must accept with probability at least
2/3 if A has P and must reject with probability at least 2/3 if dist(A, P ) ≥ ε.
Definition 6. Property P is testable if for all ε > 0 there are ε-testers making
a number of queries which is upper-bounded by a function depending only on ε.
We allow different ε-testers for each ε > 0. The situation is similar to thatfamiliar from circuit complexity (cf. Straubing [30]), where we have uniform andnon-uniform cases, see, e.g., Alon and Shapira [7]. Our results hold in both casesand so we will not distinguish between them.

144

2.2

C. Jordan and T. Zeugmann

Logical Definitions

We use a predicate logic with equality that does not contain function symbols.
There are no ordering symbols such as ≤ or arithmetic relations such as PLUS.
The first-order logic of vocabulary τ is built from the atomic formulas xi = xj
and Ri (x1 , . . . , xai ) for variable symbols xj and predicate symbols Ri ∈ τ byusing the Boolean connectives and quantifiers ∃ and ∀ in the usual way.
Formula ϕ of vocabulary τ is interpreted as usual and defines property P :={A | A ∈ STRUC (τ ) and A |= ϕ}. Lower-case Greek letters ϕ, ψ and γ referto first-order formulas and x, y, and z to first-order variables. Our classification
definitions are from Börger et al. [9] except that we omit function symbols. The
following is for completeness, where N = {0, 1, . . .} is the set of natural numbers.
Definition 7. A prefix vocabulary class is specified as [Π, p]e , where Π is astring over the four-character alphabet {∃, ∀, ∃∗ , ∀∗ }, p is either the special phrase‘all’ or a sequence over N and the first infinite ordinal ω, and e is ‘=’ or λ.
The first-order sentence ϕ := π1 x1 π2 x2 . . . πr xr : ψ in prenex normal form,
with quantifiers πi and quantifier-free ψ, is a member of the prefix vocabularyclass given by [Π, (p1 , p2 , . . .)]e , where pi ∈ N ∪ {ω} iff
1. The string π1 π2 . . . πr is contained in the language specified by Π when Π
is interpreted as a regular expression.
2. If p is not all, at most pi distinct predicate symbols of arity i appear in ψ.
3. Equality (=) appears in ψ only if e is ‘=’.
Here, Π is the pattern of quantifiers, p is the maximum number of predicate
symbols of each arity and e determines if the equality symbol is permitted.
A prefix class is testable if every formula in it expresses a testable property
for every vocabulary in which it is evaluable. An extension of a vocabulary τ isany vocabulary formed by adding a new, distinct predicate symbol to τ .
Lemma 1. Let ϕ be a formula in the first-order logic of vocabulary τ and let τ 0
be any extension of τ . If ϕ defines a property that is testable in the context of τ ,then the property of type τ 0 defined by ϕ is also testable.
Proof. Let ϕ define property P of type τ and property P 0 of type τ 0 . Assume
the “new” predicate symbol in τ 0 is N of arity a. Let Tετ be an ε-tester for P .
We will show that it is also an ε-tester for P 0 . Assume A ∈ STRUC (τ 0 ) has
property P 0 . Removing the N predicate, the corresponding A0 ∈ STRUC (τ ) has
property P and so Tετ accepts with probability at least 2/3, as desired.
Assume that dist(A, P 0 ) ≥ ε and again let A0 be the structure of type τformed by removing the N predicate from A. By the definition of distance,Pai
B
and RAi (x) ⊕ Ri (x)}|1≤i≤s |{x | x ∈ U
0Ps
dist(A , P ) = min
≥
ai
B∈P
i=1 n
P
ai
B
and RAi (x) ⊕ Ri (x)}|1≤i≤s |{x | x ∈ U
P
dist(A, P 0 ) = min
≥ ε.
s
B∈P
na + i=1 nai
The tester rejects such A with probability at least 2/3, as desired.

tuRelational Properties Expressible with One ∀ Quantifier Are Testable

145

Testable properties remain testable when the vocabulary is extended. So it
suffices to consider the minimal relevant vocabulary. A prefix class is untestable if
it contains an untestable property. Simple modifications of the proof of Lemma 1
give the corresponding results for the variations considered in the next section.

3

Variations of Relational Property Testing

In Definition 3, any difference in low-arity relations is asymptotically dominatedby the number of high-arity tuples. However, there are situations where this is
not ideal. Consider (not necessarily admissible, vertex) 3-colored graphs with thevocabulary τC := (E 2 , R1 , G1 , B 1 ). We might wish to test if the given coloring is
admissible. In large graphs, this is equivalent to testing if the graph is 3-colorable
and ignores the given coloring. We need a different model for our task.
Here we give two alternate definitions for the distance between structures.
In testing we wish to distinguish structures that have a desired property andthose that are far from the property, and so modifying the definition of distancechanges the task of testing. As in Definition 3, the symbol ⊕ is exclusive-or.
Definition 8. Let A, B ∈ STRUC n (τ ) be structures. Then, the r-distance is
B|{x | x ∈ U ai and RA
i (x) ⊕ Ri (x)}|
.
1≤i≤s
nai

rdist(A, B) := max

While Definition 3 gave equal weight to each tuple regardless of its arity, theabove gives equal weight to each relation. However, loops in graphs and othersubtypes of relations are similar to low-arity relations.
Definition 9. Let R be a relation with arity a. The subtypes of R are thepartitions of {1, . . . , a}.
For example, {{1}, {2}} is a subtype of the edge predicate E for graphs. This
corresponds to the set of pairs of E for which the element in position 1 of the pairoccurs only in position 1 and the element in position 2 occurs only in position 2.
That is, this subtype is the set of edges that are not loops. The subtype {{1, 2}}corresponds to the set of loops. This is more formally defined as follows.
Definition 10. Let R be a relation with arity a and S be a subtype of R, i.e.,
o
n
|S|
|S|
S = {t11 , . . . , t1b1 }, . . . , {t1 , . . . , tb|S| } .
Tuple (x1 , . . . , xa ) belongs to S if for all ti1 , it is the case that xti1 = xtij for all
j and, if xu = xv for some u, v then u and v occur in the same element of S.
We define the S-distance between structures, for a subtype S of relation Ri .
Definition 11. Let A, B ∈ STRUC n (τ ) be structures with universe U , and let
S be a subtype of relation Ri ∈ τ . Then, the S-distance between A and B is
S-dist(A, B) :=|{x | x ∈ U ai , x belongs to S and RiA (x) ⊕ RiB (x)}|
.
n|S|

146

C. Jordan and T. Zeugmann

If the S-dist for all subtypes of all relations is small, no query has a highprobability of finding a difference. Denote the set of subtypes of R by SUB(R).
Definition 12. For A, B ∈ STRUC n (τ ), the mrdist is
mrdist(A, B) := max

max

1≤i≤s S∈SUB(Ri )S-dist(A, B) .

We let T be the set of testable properties using the dist definition, Tr be theset of testable properties using the rdist definition and Tmr be the set of testableproperties using the mrdist definition. It is easy to show the following.
Theorem 1. Let τ be a vocabulary and A, B ∈ STRUC n (τ ). Then,dist(A, B) ≤ rdist(A, B) ≤ mrdist(A, B).
Assume a tester distinguishes between structures A having some property P
and those for which mrdist(A, P ) ≥ ε. Theorem 1 trivially implies that it also distinguishes between structures A that have P and those for which rdist(A, P ) ≥ ε.
The case with rdist and dist is analogous, which proves the following.
Corollary 1. Tmr ⊆ Tr ⊆ T .
Of course it is always desirable to show that such containments are strict.
We show the separations by encoding the following language of binary strings,←
where u denotes the usual reversal of string u.
← ←Theorem 2 (Alon et al. [4]). The language L = √{uuv v}, where u and v arestrings over {0, 1} is not testable with complexity o( n).
In some vocabularies, e.g., binary strings and loop-free graphs, all three definitions are equivalent. However, we will show the following.
Theorem 3. Tmr ⊂ Tr ⊂ T .
Proof. The inclusions are by Corollary 1 and so only the separations remain. We
first show that T \Tr is not empty. We use the vocabulary τC := (E 2 , S 1 ).
We will show P1 ∈ T \Tr , where P1 ⊆ STRUC (τC ) is the set of structures
where the S assignments encode the language L of Theorem 2. That is, A has P1
if there is some 0 ≤ k ≤ n/2 such that for all 0 ≤ i < k, S(i) is true iff S(2k−1−i)is true and for all 0 ≤ j < (n − 2k)/2, S(2k + j) is true iff S(n − 1 − j) is true.
The property uses only the low-arity relation S; the E relation is for “padding”
to make P1 testable under the dist definition for distance.
We first show that P1 is in T . A structure with a universe of odd size cannot
have P1 . A tester can begin by checking the parity of n and rejecting if it is odd
and so we assume in the following that the size of the universe is even.
Lemma 2. Property P1 is testable under the dist definition for distance.

Relational Properties Expressible with One ∀ Quantifier Are Testable

147

← ←

Proof. For any (even) n, 1n is of the form uuv v. Given A, we create A0 bychanging all S(i) assignments to be true. This involves at most n modifications
and so dist(A, P1 ) ≤ dist(A, A0 ) = O(n)/Θ(n2 ) < ε, where the final inequality
holds for sufficiently large n. Let N (ε) be the smallest value of n for which it
holds. The following is an ε-tester for P1 , where the input has universe size n.
1. If n < N (ε), query all assignments and output whether the input has P1 .
2. Otherwise, accept.
If A has P1 , we accept with zero error. If dist(A, P1 ) ≥ ε, then n < N (ε). In
this case we query all assignments and reject with zero error.
t Lemma 2u
It remains to show that P1 is not testable when using the rdist definition for
distance. We do this by showing that it would contradict Theorem 2.
Lemma 3. Property P1 is not testable under the rdist definition for distance.
Proof. Suppose there exist Tr -type ε-testers T ε for all ε > 0. We will show thatthe following is an ε-tester using Definition 3 for the language L of Theorem 2.
Let the input be w, a binary string of length n.
1. Run T ε and intercept all queries.
2. When a query is made for S(i), return the value of S(i) in w.
3. When a query is made for E(i, j), return 0.
4. Output the decision of T ε .
We run T ε on the A ∈ STRUC n (τC ) that agrees with w on S and where all
E assignments are false. If w ∈ L, then any such A has property P1 and so ourtester accepts with probability at least 2/3.
Assume dist(w, L) ≥ ε. Then, rdist(A, P1 ) = dist(w, L) ≥ ε and so our tester
rejects with probability at least 2/3. These are testers for the untestable languaget Lemma 3
uof Theorem 2, and so P1 is untestable under the rdist definition.
Lemmata 2 and 3, together with Corollary 1 show Tr ⊂ T . The separation
Tmr ⊂ Tr is shown in a similar way, using a property with sufficient “padding”
to make Tr testing simple but Tmr testing would contradict Theorem 2.
An example is the property of graphs where the “loops” E(i, i) encode thelanguage from Theorem 2. We omit the details due to space.
t Theorem 3uThere exist properties that are testable in the rdist sense but not in themrdist sense. However, the definition of subtypes and Tmr testability allows
for a simple mapping between vocabularies such that rdist-testability of certainclasses of properties implies mrdist-testability of the same classes. For theseclasses, proving testability in the rdist sense is equivalent to proving it in themrdist sense, and so it suffices to use whichever definition is more convenient.
Lemma 4 is given in the context of the classification problem for first-orderlogic but it is not difficult to prove similar results in other contexts. Our main
result is the testability of Ackermann’s class with equality, which is of the form
required by the lemma. A formula is testable if the property it defines is testable.

148

C. Jordan and T. Zeugmann

Lemma 4. Let C := [Π, all]= be a prefix vocabulary class. Then, C is testablein the rdist sense iff it is testable in the mrdist sense.
Proof. Recalling Theorem 3, Tmr testability implies Tr testability. We prove Tr
testability of such prefix classes implies Tmr testability using Lemma 5. In thefollowing, S(n, k) is the Stirling number of the second kind.
Lemma
5. Let C = [Π, (p1 , p2 , . . .)]= be a prefix vocabulary class and let qj =P
pS(i,j). If C 0 = [Π, (q1 , q2 , . . .)]= is Tr testable, then C is Tmr testable.
i≥j iProof. Let ϕ ∈ C be arbitrary and assume that the predicate symbols of ϕ are{R11 , R21 , . . . , Rp11 , R12 , . . .}, where the arity of Rji is i. We construct a ϕ0 ∈ C 0 andshow that Tr testability of ϕ0 implies Tmr testability of ϕ. In ϕ0 we will use adistinct predicate symbol for each subtype of each Rji in ϕ. A subtype S of Rji
such that |S| = k is a partition of the integers {1, . . . , i} into k non-empty sets
and so there are S(i, k) such subtypes. We therefore require a total of qk distinct
predicate symbols of arity k.
For example, we will map the “loops” in a binary predicate E to a newmonadic predicate and the non-loops to a separate binary predicate. Formally,
we let t map the subtypes of a predicate to the sets of tuples comprising thesubtypes. For our example of a binary predicate, (0, 1) ∈ t({{1}, {2}}) and(0, 0) ∈ t({{1, 2}}). Next, we let r be a bijection from the subtypes of predicates to their new names, the predicate symbols that we will use in ϕ0 .
We create ϕ0 by modifying ϕ. Replace all occurrences of Rji (x1 , . . . , xi ) with

_





(x1 , . . . , xi ) ∈ t(S) ∧ r(S, Rji )(y)  .

S∈SU B(Rji )Note that (x1 , . . . , xi ) ∈ t(S) is an abbreviation for a simple conjunction, e.g.,x1 6= x2 ∧ x1 6= x3 ∧ · · · . Likewise, y is an |S|-ary tuple, formed by removing the
duplicate components of (x1 , . . . , xi ). The implicit mapping from (x1 , . . . , xi ) isinvertible given S. To continue our example of a binary predicate E, we would
replace all occurrences of E(x, y) in ϕ with([x = y ∧ E1 (x)] ∨ [x 6= y ∧ E2 (x, y)]) .
We assume that ϕ0 is Tr testable, and so there exists an ε-tester T ε for it. We
run this tester and intercept all queries. For a query to r(S, Rji )(y), we returnthe value of Rji (x1 , . . . , xi ). This is possible because r is a bijection, and so we
can retrieve S and Rji using its inverse. Then, we can reconstruct the full i-ary
tuple (x1 , . . . , xi ) from y and S.

Relational Properties Expressible with One ∀ Quantifier Are Testable

149

The tester implicitly defines a map1 from structures A which we wish totest for ϕ to structures A0 which we can test for ϕ0 . Given an A |= ϕ, thecorresponding A0 |= ϕ0 and so T ε will accept with probability at least 2/3.
We map each subtype S to a distinct predicate symbol with arity |S|. Therefore, for any structures A, B, the implicit mapping to A0 , B 0 is such that
mrdist(A, B) = rdist(A0 , B 0 ).
For an A such that mrdist(A, P = {B | B |= ϕ}) ≥ ε, we simulate T ε on an
A0 such that rdist(A0 , P 0 = {B 0 | B 0 |= ϕ0 }) ≥ ε. The tester T ε rejects withprobability at least 2/3, as desired.
t Lemma 5uProving Tr testability for [Π, all]= implies proving it for all (q1 , . . .) that are “images” of some (p1 , . . .) and so Lemma 5 is stronger than required. ut Lemma 4

4

The Classification Problem for Testability

Here we consider the classification problem of first-order logic for testability,
inspired by the classification problem for decidability and results in testability
such as those by Alon et al. [2]. The goal is a complete classification of the prefix
vocabulary classes of first-order logic into testable and untestable classes.
We first outline the traditional classification problem, focusing on results withparallels to results in testing. See Börger et al. [9] for the complete classificationand proofs. Then we prove the testability of Ackermann’s class with equality.
4.1

Classification SimilaritiesLöwenheim [20] proved the decidability of monadic first-order logic, and McNaughton and Papert [21] showed that it (with ordering and some arithmetic)characterizes the star-free regular languages. The testability of this logic is thenimplied by a result of Alon et al. [4]. Using instead Büchi’s [10] result thatmonadic second -order logic characterizes the regular languages, the parallel iswith Skolem’s [28] extension of Löwenheim’s result to second-order logic.
Skolem [29] showed that [∀∗ ∃∗ , all ] is a reduction class. Alon et al. [2] foundan untestable graph property (an encoding of graph isomorphism) expressible in[∀∗ ∃∗ , (0, 1)]= , a class close enough to Skolem’s [29] to be interesting.
Alon et al. [2] also proved that [∃∗ ∀∗ , (0, 1)]= is testable. The class [∃∗ ∀∗ , all ]=is known as Ramsey’s class and its decidability was shown by Ramsey [23].
1Explicitly, map A to an A0 with the same universe size, where y ∈ r(S, Rji ) in A0 if(x1 , . . . , xi ) ∈ Rji in A. Note that we have not yet defined the assignments of tuples ywith duplicate components. By construction, the assignments of these tuples do notaffect ϕ0 and so any reasonable convention will do. We define that z 6∈ Q where z
is any tuple with at least one duplicate component and Q is any predicate symbol
in ϕ0 . The resulting map is injective but not necessarily surjective.

150

5

C. Jordan and T. Zeugmann

Ackermann’s Class with Equality

Above, we saw several similarities between the classifications for decidability
and testability. Here we give an additional example: [∃∗ ∀∃∗ , all]= . Ackermann [1]proved the decidability of this class without equality. If we allow equality anda unary function symbol, the result is Shelah’s class, which Shelah [27] proved
decidable. Unlike the decidable classes above, Shelah’s class does not have thefinite model property and it would be interesting to determine if it is testable.
Kolaitis and Vardi [17] showed the satisfiability problem for Ackermann’sclass with equality is complete for NEXPTIME and that a 0-1 law holds forexistential second-order logic where the first-order part belongs to [∃∗ ∀∃∗ , all]= .
The main goal of this section is Theorem 4. Recalling Theorem 3, this also
implies that such properties are testable in the dist and rdist senses. If the vocabulary consists of a single relation, the rdist and dist definitions are equivalent
to the dense hypergraph model. We therefore obtain the corresponding resultsin the dense hypergraph and dense graph models as special cases.
We denote the set of monadic predicate symbols in a vocabulary τ by M :={Ri | Ri ∈ τ and ai = 1}. The set of assignments of the symbols in M foran element in a universe is called the color of the element and there are 2|M |possible colors. We define Col(A, c) to be the set of colors that occur at least ctimes in A.
Theorem 4. All formulas in [∃∗ ∀∃∗ , all]= define properties that are in Tmr .
Proof. Ackermann’s class with equality is [∃∗ ∀∃∗ , all]= and so it suffices to show
the testability of property P of type τ = (R1a1 , . . . , Rsas ) defined by formulaϕ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ, where ψ is quantifier-free. We can trivially test
any ϕ that has only finitely-many models with a constant number of queries andzero error, and so it suffices to assume that ϕ has infinitely-many models.
The class [∃∗ ∀∃∗ , all]= is of the form required by Lemma 4 and so it is mrdisttestable iff it is rdist-testable. It therefore suffices to show that P is testable in
the rdist sense. We will show that the following is an ε-tester in the rdist sense
for P on input A ∈ STRUC n (τ ). Here, k := k(τ, ε) is the number of elements
queried and N := N (ϕ, τ, ε) is a constant, both of which are determined below.
Note the actual number of queries in step 2 is not exactly k, but rather a constantmultiple of it depending on τ . Finally, we explicitly give κ := κ(ϕ, τ ) below.
1. If n < N , query all of A and decide exactly whether A has P .
2. Uniformly and independently choose k members of the universe of A andquery all monadic predicates on the members in this sample.
3. Search over all A0 ∈ STRUC κ (τ ). Accept if we find an A0 such that A0 |= ϕand the colors in our sample are a subset of Col(A0 , a + 1).
4. Otherwise, reject.
We must show that the tester accepts if A |= ϕ and rejects if rdist(A, P ) > ε,with probability at least 2/3 in both cases. We do this by showing that withprobability at least 2/3, we get a “good” sample in step 2 (cf. Lemma 6). A

Relational Properties Expressible with One ∀ Quantifier Are Testable151“good” sample is one that contains all colors of A that occur on at least anε/(2 · 2|M | ) fraction of the elements of A and no colors that occur on at most aelements. We then show that the tester is correct if it obtains a good sample.
Lemma 6. There is a constant k such that, with probability at least 2/3, thetester obtains a sample that contains all colors that occur at least εn/(2 · 2|M | )times in A and no colors that occur at most a times.
Proof. The probability that any particular query misses a fixed color that occurs
on at least an ε/(2 · 2|M | ) fraction of A is at most (1 − ε/(2 · 2|M | )). Moreover, theprobability that we miss such a fixed color after k independent queries is at most
(1 − ε/(2 · 2|M | ))k . There are at most 2|M | such colors, and so the probability of
our sample containing at least one representative of all such colors is at leastε/2
1 − 1 − |M |2

k !2|M |.

p
The |M | is a constant, and we take k such that this probability is at least 2/3.
Next, the probability of a particular query seeing a fixed color that occurs
at most a times is at most a/n and the probability that k independent queries
miss it is at least (1 − a/n)k . There are at most 2|M | such colors, and so the2|M |k. The k and |M |probability that we miss all of them is at least (1 − a/n)
are now
p constant, and we let N be such that for n > N this probability is atleast 2/3.
p
2
The probability of a “good” sample is at least 2/3 = 2/3.
t Lemma 6u
We now show that if A |= ϕ, the tester will accept if it obtains a good sample.
We begin with Lemma 7.
Lemma 7. Let A be a model of ϕ such that #(A) > N and let
P s P aiaiai −jκ := a + 3b a + 2 i=1 j=1 ( j )a
+ 2|M | (a + 1).
Then, there is an A0 |= ϕ such that #(A0 ) = κ and Col(A, a+1) ⊆ Col(A0 , a+1).
Proof. Assume that N > κ. The structure A is a model of ϕ, and so there exists
at least one tuple of a elements (u1 , . . . , ua ) such that ϕ is satisfied when theexistential quantifiers bind ui to xi . We consider the xi and the substructure
induced by them to be fixed, and referto this substructure as Ax .
P s P ai
ai
ai −j
i=1
j=1 ( j )a
There are at most κ2 := a + 2
many distinct structures
constructed by adding an element labeled y to Ax when we include the structures
where the label y is simply placed on one of the xi . We let v ≤ κ2 be the numberof such structures that occur in A and assume there is an enumeration of them.
For each of these v substructures there exist b elements, w1 , . . . , wb , suchthat when we label wi with zi , the structure induced by (x1 , . . . , xa , y, z1 , . . . , zb )

152

C. Jordan and T. Zeugmannmodels ψ. We construct Ai,j for 1 ≤ i ≤ 3 and 1 ≤ j ≤ v such that Ai,j is acopy of the w1 , . . . , wb used for the j-th structure. We connect each Ai,j to Ax
in the same way as in A, modifying assignments on tuples (Ax ∪ Ai,j )ak .
For each wh in Ai,j , we consider the case where y is bound to wh . By construction the substructure induced by (x1 , . . . , xa , y) occurs in A. We assume itis the k-th structure and use the elements of Ai+1 mod 3,k to construct a structure satisfying ψ. We modify the assignments of tuples as needed to create astructure identical to that in A satisfying ψ. Note that by construction all ofthese assignments are of tuples that contain wh and at least one element from
Ai+1 mod 3,k . The resulting structure, which we call A1 , is a model of ϕ. Before
this step we have not modified any assignments “spanning” the “rows” Ai,j of
A1 and so there are no assignments that we modify more than once.
However, there may be some color from Col(A, a + 1) that does not appear
a+1 times in A1 . We therefore add a new block, denoted Ae , of at most 2|M | (a+1)
elements which consists of a + 1 copies of each color from Col(A, a + 1). Eachof these colors occurred at least a + 1 times in A, and so for each such color C,
there is an element q in A with color C such that q is not part of Ax . If thesubstructure induced by (Ax , q) in A is the j-th structure in our enumeration,then we do the following for each member p of Ae that has the same color as q.
First, we make the substructure induced by (Ax , p) identical to that induced by(Ax , q) in A. Next, we make the substructure induced by (p, A1,j ) identical tothat induced by q and the corresponding zi in A. All of these modifications areon tuples containing a p ∈ Ae and so we do not modify any tuples more thanonce. We call this structure A2 .
Finally, so far we only have an upper-bound on the size of A2 while the lemma
states it to be exactly of size κ. We therefore pad in the following simple way2 .
We know that N > κ > 2|M | a and so there is a color that occurs at least a + 1
times in A. If #(A2 ) < κ, we simply make an additional κ − #(A2 ) many copiesof this color in Ae and modify the assignments of tuples containing these newelements in the same manner as above. The resulting A0 has size κ and satisfies
the requirements of the lemma.
t Lemma 7u
For structures A such that #(A) > N , the colors in a good sample are asubset of Col(A, a + 1). If A |= ϕ and our tester obtains a good sample, thenLemma 7 implies that our tester will find an A0 satisfying the conditions of step
3 and will therefore accept. The tester obtains a good sample with probability
at least 2/3, and so the tester accepts such A with at least the same probability.
Next, assume that rdist(A, P ) ≥ ε. In this case we must show that the tester
rejects with probability at least 2/3. It is easiest to show the contrapositive: if thetester accepts with probability strictly greater than 1/3, then rdist(A, P ) < ε.
If we accept a structure A with probability strictly greater than 1/3, thenwe must accept it when we obtain a good sample. We construct a B such that
B |= ϕ and rdist(A, B) < ε from the A0 that the tester must find to accept. We
begin with Lemma 8, which we will use to “grow” smaller models.
2

One could instead change the tester to search structures with size at most κ.

Relational Properties Expressible with One ∀ Quantifier Are Testable

153

Lemma 8. Let ϕ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ be a formula with vocabulary τ
where ψ is quantifier-free and A ∈ STRUC (τ ) be such that A |= ϕ. Additionally,let B ∈ STRUC (τ ) be any structure containing A as an induced substructuresuch that #(B) = #(A) + 1. If the additional element of B has a color that
occurs at least a + 1 times in A, then we can construct a B 0 |= ϕ by modifying
at most a constant number of non-monadic assignments in B.
Proof. B contains an induced copy of A and one additional element, which wewill denote by q. By assumption, A is a model of ϕ and therefore contains an
a-tuple (u1 , . . . , ua ) such that the formula is satisfied when xi is bound to ui . In
addition, there are at least a + 1 elements in A that have the same color as q.
Therefore, there is at least one such element p that is not one of the ui . We will
make q equivalent to p without modifying any monadic assignments.
We first modify the assignments needed to make the structure induced by(x,. , xa , q) identicalto that induced by (x1 , . . . , xa , p). This requires at most1Ps . .Pai
ai ai −ja=O(1) modifications, all of which are non-monadic. There
i=1
j=1 j
must be (v1 , . . . , vb ) in A such that ψ is satisfied when zi is bound to vi andy to p. We modify the assignments needed to make the structure induced by(q,. . . , vb ) identicalto that induced by (p, v1 , . . . , vb )3 . This requires at mostPsv1 , Pai
ai ai −j= O(1) modifications, all of which are non-monadic. The
i=1
j=1 j bresult has #(A) + 1 elements, models ϕ and was constructed from B by making
a constant number of modifications to non-monadic assignments. u
t Lemma 8
Let A be the structure that the tester is running on and A0 be the structure
found in step 3 of the tester. As mentioned above, we will construct a B |= ϕfrom A0 such that B |= ϕ and rdist(A, B) < ε.
Note that there must exist at least one color in Col(A, εn/(2 · 2|M | )) andassume that N is large enough that εn/(2 · 2|M | ) ≥ a + 1. We first make aconstant sized portion of A identical to A0 . This requires at most O(1)-many
modifications to each relation. All colors in Col(A, εn/(2 · 2|M | )) occur at least
a+1 times in A0 , allowing us to recursively apply Lemma 8 and add the elementsof A that have colors in Col(A, εn/(2 · 2|M | )). This entails making O(1)-many
modifications to non-monadic relations (and none to monadic relations) at each
step, for a total of O(n) modifications to the non-monadic relations.
Finally, we consider the elements of A that have colors occurring at mostεn/(2 · 2|M | ) times. There are at most 2|M | such colors and at most εn/2 elements with these colors. We change the monadic assignments on such elements
as required to give them colors contained in Col(A, εn/(2 · 2|M | )). This requires
at most εn/2 modifications to each of the monadic assignments. We again recursively apply Lemma 8 to A, making O(1) modifications to non-monadic assignments at each step. The resulting structure is B and is such that B |= ϕ.
We now show that rdist(A, B) < ε. If Ri is a monadic relation, then the i-thterm of the maximum in Definition 8 is at most ε/2 + o(1). If Ri has arity atleast two, then the i-th term of the maximum is O(n)/Ω(n2 ) = o(1). All o(1)3The case where vi = p can be handled by replacing vi with q in (q, v1 , . . . , vb ).

154

C. Jordan and T. Zeugmann

terms can be made arbitrarily small by choosing N (ϕ, τ, ε) appropriately andso we can assume that all terms are strictly less than ε. The maximum is thenstrictly less than ε and so rdist(A, B) < ε as desired.
t Theorem 4u6Conclusion

We considered a generalization of property testing which we call relational property testing. In Section 3 we showed the relationships between variations of ourdefinitions. The “best” definition depends on the problem in question.
Relational databases are perhaps the most obvious example of massive structures where it would be promising to consider applications of property testing.
Relational property testing is a natural way to characterize this problem. In
addition, properties of databases are often given by queries written in formal
languages such as SQL and so it is very natural to consider the testability ofproperties expressible in various syntactic restrictions of formal languages.
Finally, we used our framework to discuss the classification problem for testability in Section 4, inspired by the classical problem for decidability. The major
result of Section 4 is the testability of Ackermann’s class with equality, in eachof the variations of relational property testing that we considered. This implies
the corresponding result in the dense graph and hypergraph models.

References[1] Ackermann, W.: Über die Erfüllbarkeit gewisser Zählausdrücke. Math. Annalen
100 (1928) 638–649[2] Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large
graphs. Combinatorica 20(4) (2000) 451–476[3] Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterizationof the testable graph properties: It’s all about regularity. In: STOC ’06: Proc.
38th Ann. ACM Symp. on Theory of Comput., NY, USA, ACM (2006) 251–260[4] Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testablewith a constant number of queries. SIAM J. Comput. 30(6) (2001) 1842–1862[5] Alon, N., Shapira, A.: A characterization of the (natural) graph properties testablewith one-sided error. In: Proc., 46th Ann. IEEE Symp. on Foundations of Comput.
Sci., FOCS 2005, Washington, DC, USA, IEEE Comput. Soc. (2005) 429–438[6] Alon, N., Shapira, A.: Homomorphisms in graph property testing. In Klazar,
M., Kratochvı́l, J., Loebl, M., Matoušek, J., Thomas, R., Valtr, P., eds.: Topics
in Discrete Mathematics. Volume 26 of Algorithms and Combinatorics. Springer(2006) 281–313[7] Alon, N., Shapira, A.: A separation theorem in property testing. Combinatorica
28(3) (2008) 261–281[8] Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications tonumerical problems. J. of Comput. Syst. Sci. 47(3) (1993) 549–595[9] Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. SpringerVerlag (1997)[10] Büchi, J.R.: Weak second-order arithmetic and finite-automata. Z. Math. Logik
Grundlagen Math. 6 (1960) 66–92

Relational Properties Expressible with One ∀ Quantifier Are Testable

155[11] Chockler, H., Kupferman, O.: ω-regular languages are testable with a constantnumber of queries. Theoret. Comput. Sci. 329(1-3) (2004) 71–92[12] Fischer, E.: The art of uninformed decisions. Bulletin of the European Association for Theoretical Computer Science 75 (October 2001) 97–126 Columns:
Computational Complexity.
[13] Fischer, E., Matsliah, A., Shapira, A.: Approximate hypergraph partitioning andapplications. Proc. 48th Ann. IEEE Symp. on Foundations of Comput. Sci., FOCS
2007 (2007) 579–589[14] Freivalds, R.: Fast probabilistic algorithms. In: Mathematical Foundations ofComputer Science 1979, Proc., 8th Symp., Olomouc, Czechoslovakia, September
3-7, 1979. Volume 74 of Lecture Notes in Computer Science., Springer-Verlag(1979) 57–69[15] Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica
32 (2002) 302–343[16] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection tolearning and approximation. J. ACM 45(4) (1998) 653–750[17] Kolaitis, P.G., Vardi, M.Y.: 0-1 laws and decision problems for fragments ofsecond-order logic. Inf. Comput. 87(1-2) (1990) 302–338[18] Leeuw, K.d., Moore, E.F., Shannon, C.E., Shapiro, N.: Computability by probabilistic machines. In Shannon, C., McCarthy, J., eds.: Automata Studies. Princeton University Press, Princeton, NJ (1956) 183–212[19] Lovász, L.: Some mathematics behind graph property testing. In Freund, Y.,
Györfi, L., Turán, G., Zeugmann, T., eds.: Algorithmic Learning Theory, 19thInternational Conference, ALT 2008, Budapest, Hungary, October 2008, Proc.
Volume 5254 of Lecture Notes in Computer Science., Springer (2008) 3[20] Löwenheim, L.: Über Möglichkeiten im Relativkalkül. Math. Annalen 76 (1915)
447–470[21] McNaughton, R., Papert, S.: Counter-Free Automata. M.I.T. Press (1971)[22] Parnas, M., Ron, D.: Testing the diameter of graphs. Random Struct. Algorithms
20(2) (2002) 165–183[23] Ramsey, F.P.: On a problem of formal logic. Proc. London Math. Soc. (2) 30(1930) 264–286[24] Rödl, V., Schacht, M.: Property testing in hypergraphs and the removal lemma.
In: STOC ’07: Proc. 39th Ann. ACM Symp. on Theory of Comput., NY, USA,ACM (2007) 488–495[25] Ron, D.: Property testing. In Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim,J., eds.: Handbook of Randomized Computing. Volume II. Kluwer Academic
Publishers (2001) 597–649[26] Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2) (1996) 252–271[27] Shelah, S.: Decidability of a portion of the predicate calculus. Israel J. Math.
28(1-2) (1977) 32–44[28] Skolem, T.: Untersuchungen über die Axiome des Klassenkalküls und über Produktations und Summationsprobleme, welche gewisse Klassen von Aussagen betreffen. Videnskapsselskapets skrifter, I. Mat.-natur kl. (3) (1919) 37–71[29] Skolem, T.: Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder
Beweisbarkeit mathematischer Sätze nebst einem Theorem über dichte Mengen.
Videnskapsselskapets skrifter, I. Mat.-natur kl. (4) (1920) 1–26
[30] Straubing, H.:
Finite Automata, Formal Logic, and Circuit Complexity.
Birkhäuser (1994)