Untestable Properties in the Kahr-Moore-Wang
ClassCharles 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. Property testing is a kind of randomized approximation inwhich one takes a small, random sample of a structure and wishes todetermine whether the structure satisfies some property or is far fromsatisfying the property. We focus on the testability of classes of first-order
expressible properties, and in particular, on the classification of prefixvocabulary classes for testability. The main result is the untestability of[∀∃∀, (0, 1)]= . This is a well-known class and minimal for untestability.
We discuss what is currently known about the classification for testability
and briefly compare it to other classifications.
Keywords: property testing, logic, randomized algorithms

1

Introduction

In property testing, we take a random sample of some large structure and wish
to distinguish between the case that it has some desired property and the casethat it is far from having the property. We focus on the testability of first-order
expressible properties, and in particular on the classification of prefix-vocabularyclasses of first-order logic for testability.
Rubinfeld and Sudan [21] and Blum et al. [4] introduced the notion of property testing in the context of formal verification. The basic idea was soon extended by Goldreich et al. [11], who represented graphs as binary functions andfocused on testing graph properties. We omit a detailed history of testing, see
the recent introduction to testing graph properties by Goldreich [10], two recent
surveys by Ron [19, 20], and older surveys by Fischer [7] and Ron [18].
We are particularly interested in the testability of properties expressible insubclasses of first-order logic, and review relevant work in Subsection 1.1.
Here, we show that there exist untestable graph properties expressible withquantifier prefix ∀∃∀ when equality is allowed (see Section 3 for a formal statement). Taking into account the related work described in Subsection 1.1 andusing the notation of Definition 7, the current classification for testability is thefollowing.
?
??

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.

Untestable Properties in the Kahr-Moore-Wang Class

177– Testable classes
1. Monadic first-order logic: [all, (ω)]= .
2. Ackermann’s class with equality: [∃∗ ∀∃∗ , all]= .
3. Ramsey’s class: [∃∗ ∀∗ , all]= .
– Untestable classes
1. [∀3 ∃, (0, 1)]= .
2. [∀∃∀, (0, 1)]= .
We are especially interested in determining the testability of variants of theGödel class (i.e., classes whose prefix contains at least ∀2 ∃) as this would suffice to complete the classification for the special case of predicate logic withequality. The above classification is consistent with several other well-knownclassifications, such as that for the finite model property (see, e.g., Chapter 6 ofBörger et al. [5], for docility (or finite satisfiability, see Kolaitis and Vardi [16])and for associated 0-1 laws for fragments of existential second-order logic (see
Kolaitis and Vardi [16]). It would be interesting to know if the classification for
testability coincides with one of these classifications.
The rest of the paper is organized as follows. First, we review related workin Subsection 1.1. Definitions and notation are in Section 2. The main result ispresented in Section 3.
1.1

Related Work

Alon et al. [3] proved that the regular languages are testable, implying thatmonadic first-order is testable given the well-known results of Büchi [6] or McNaughton and Papert [17]. Alon et al. [2] were the first to directly consider theclassification problem for testability, restricted to properties of undirected, loopfree graphs. They proved the testability of all such properties expressible byprenex sentences with quantifier prefix ∃∗ ∀∗ , and also showed that there exists
an untestable property expressible with quantifier prefix ∀∗ ∃∗ (examining theproof shows that ∀12 ∃5 suffices).
Both of these are (restrictions of) well-known classes. Jordan and Zeugmann extended [13] the positive result to the full Ramsey’s class ([∃∗ ∀∗ , all]= ),proved [12] the testability of Ackermann’s class with equality ([∃∗ ∀∃∗ , all]= ),and sharpened [14] the negative result to prefixes ∀3 ∃, ∀2 ∃∀, ∀∃∀∃ and ∀∃∀2 (ondirected graphs with equality). This paper sharpens these last three prefixes andproves that [∀∃∀, (0, 1)]= is a minimal prefix class for untestability. This particular class is the restriction of the Kahr-Moore-Wang [15] class (plus equality) to
directed graphs.
It is easy to show that [∀∃∀, (0, 1)] (even without equality) has infinity axioms1 . Vedø [22] showed that a 0-1 law does not hold for second-order existential
logic when the first-order part is in this class (again, even without equality).
The current paper sharpens some (prefixes ∀2 ∃∀, ∀∃∀∃, ∀∃∀2 ) of the results of
Jordan and Zeugmann [14] and so we briefly outline the improvement that allows
us to minimize the prefix considered. The untestable property considered in [14]1

An infinity axiom is a sentence that has only infinite models.

178

C. Jordan and T. Zeugmannis closely related to the untestable property of Alon et al. [2], but modified tominimize the number of quantifiers used. These properties are essentially firstorder expressible versions of checking an explicitly given isomorphism between
two graphs2 . In fact, restricting the properties to checking an explicitly given
isomorphism between undirected, bipartite graphs (see Figure 1(a)) maintains
hardness for testing. However, graph isomorphism seems to require one to discussat least four vertices simultaneously (because one wishes to state that an edge
is present iff its image is present and the edges are disjoint in general).

(a) A graph with Pb(b) A graph with Pe(c) A graph with Pf

Fig. 1. Properties Pb , Pe and Pf

Sharing one of the partitions (see Figure 1(b)) would seem to remove theneed for four quantifiers. The resulting property is perhaps closer to a variantof function isomorphism, e.g., for functions f, g : [n] → {0, 1}n where the bit i off (j) is 1 if there is an edge from j in the leftmost partition to i in the middle
partition and likewise for g(j) and the right partition. This property is not firstorder expressible, but there is a somewhat tedious first-order encoding that issimilar (see Figure 1(c) and the formula in Section 3).
The connection with function isomorphism allows us to leverage recent workon the testability of (Boolean) function isomorphism and use recent ideas andtechniques from Alon and Blais [1] to prove Lemma 1.

2

Preliminaries

The goal in property testing is always to distinguish structures that have someproperty from those that are far from having the property. Here, we focus on
first-order expressible properties of directed graphs and so we begin with thenecessary definitions.
Definition 1. A graph is an ordered pair G = (V, E), where V is a finite set
and E ⊆ V × V a binary relation defined on V .
We generally identify V with the first n naturals [n] := {1, . . . , n} and call#(G) := |V | = n the size of a graph G. Let G n be the set of graphs of size n and
2Graph isomorphism is generally hard for testing, see, e.g., Fischer and Matsliah [8].

Untestable Properties in the Kahr-Moore-Wang Class179

G := ∪n≥0 G n be the set of all (finite) graphs. Note that our graphs are directed
and may contain loops.
A property P ⊆ G of graphs is any set of graphs. We are particularly interested in first-order expressible properties. Our logic is a basic first-order predicate
logic with equality. There are no function or constant symbols. We focus on firstorder properties of graphs, and so the only predicate symbol (besides the special
symbol =) is the binary edge symbol E.
A sentence ϕ defines a property in the natural way,Pϕ := {G | G ∈ G, G |= ϕ} .
We require a distance between graphs and properties, which we define in thefollowing way. We denote the symmetric difference of sets by 4 and let E A andE B be the edge predicates of A and B, respectively.
Definition 2. Let A = (V, E A ) and B = (V, E B ) be two graphs defined suchthat |V | = n. The distance between A and B isdist(A, B) := |E A 4 E B |/n2 .
The distance generalizes to properties in the obvious way, dist(A, P ) :=minB∈P dist(A, B). Definition 2 results in a typical model of testing based on
the dense graph model introduced by Goldreich et al. [11]. We now proceed to
the remaining testing definitions.
Definition 3. An ε-tester for property P is a randomized algorithm that makes
queries for the existence of edges in a graph A. The tester must accept withprobability at least 2/3 if A has P and must reject with probability at least 2/3
if dist(A, P ) ≥ ε.
Definition 4. Property P is called testable if there is some function c(ε) andfor every ε > 0, an ε-tester for P such that the tester makes at most c(ε) queries.
Note that the query complexity is bounded by a function that does notdepend on the size of the graphs. We allow different ε-testers for each ε > 0 andso this is a non-uniform model. However, we are focused on proving untestability
and our results hold even in the non-uniform case.
Next, we will define indistinguishability, a relation on properties introduced
by Alon et al. [2] that preserves testability. However, testers can focus on loops
and distinguish between structures that have an asymptotically small difference(because the number of loops is asymptotically dominated by the number of
non-loops). We therefore begin with an alternative definition of distance (using
this in place of Definition 2 makes testing (strictly) more difficult, but our result
holds even when we use Definition 2). In the following, ⊕ denotes exclusive-or.
Definition 5. Let n ∈ N and let U be any universe such that |U | = n. Furthermore, let A = (U, E A ) and B = (U, E B ) be any two graphs with universe U . For
notational convenience, let
d1 (A, B) :=|{x | x ∈ U and E A (x, x) ⊕ E B (x, x)}|
, and
n

180

C. Jordan and T. Zeugmann

d2 (A, B) :=|{(x1 , x2 ) | x1 , x2 ∈ U, x1 6= x2 , and E A (x1 , x2 ) ⊕ E B (x1 , x2 )}|.
n(n − 1)

The mr-distance between A and B is
mrdist(A, B) := max {d1 (A, B), d2 (A, B)} .
Definition 6. Two properties P and Q of graphs are indistinguishable if they
are closed under isomorphisms and for every ε > 0 there exists an Nε such thatfor any graph A with universe of size n ≥ Nε , if A has P then mrdist(A, Q) ≤ ε
and if A has Q then mrdist(A, P ) ≤ ε.
An important property of indistinguishability is that it preserves testability.
The proof of the following is analogous to that given in Alon et al. [2].
Theorem 1. If P and Q are indistinguishable, then P is testable if and only if
Q is testable.
In fact, as the proof constructs an ε-tester for P by iterating an ε/2-tester for
Q three times, one can also relate the query complexities of P and Q. Many proofsof hardness for testability rely on Yao’s Principle [23], an interpretation of von
Neumann’s minimax theorem for randomized computation. For completeness,
we state the version that we use.
Principle 1 (Yao’s Principle) If there is an ε ∈ (0, 1) and a distribution overG n such that all deterministic testers with complexity c have an error-rate greaterthan 1/3 for property P , then property P is not testable with complexity c.
The definition of “testable” is of course our usual one involving random
testers. In general, one seeks to show that for sufficiently large n and someincreasing function c := c(n), there is a distribution of inputs such that all
deterministic testers with complexity c have error-rates greater than 1/3.
Finally, we briefly define the notation we use to specify prefix-vocabularyclasses. See Börger et al. [5] for details and related material.
Definition 7. Let Π be a string over the four-character alphabet {∃, ∀, ∃∗ , ∀∗ }.
Then [Π, (0, 1)]= is the set of sentences in prenex normal form which satisfy thefollowing conditions.
1. The quantifier prefix is contained in the regular language given by Π (fortechnical reasons, one usually treats ∃ and ∀ as matching the relevant quantifier and also the empty string).
2. There are zero (0) monadic predicate symbols.
3. In addition to the equality predicate (=), there is at most one (1) binary
predicate symbol.
4. There are no other predicate symbols.
That is, [Π, (0, 1)]= is the set of prenex sentences in the logic defined above whose
quantifier prefixes match Π. If the second component of the specification is all,then conditions two and three are removed (any number of predicate symbols
with any arities are acceptable).

Untestable Properties in the Kahr-Moore-Wang Class

3181

An Untestable Property

Our goal in this section is Theorem 2.
Theorem 2. The prefix class [∀∃∀, (0, 1)]= is not testable.
We begin by outlining the proof. First, we define Pf , a property expressible
in the class [∀∃∀, (0, 1)]= which, as described in Subsection 1.1, is in some sensea somewhat tedious but first-order expressible variant of checking (explicit) isomorphism of undirected bipartite graphs in tripartite graphs. We then define avariant P2 , in which the isomorphism is not explicitly given and we must test
whether there exists some suitable isomorphism. Although this increases thecomplexity of deciding the problem from checking an isomorphism to finding
one, it does not change hardness for testing. We show that P2 and Pf are indistinguishable and so P2 is testable√iff Pf is testable. Finally, we prove directlythat P2 is untestable, even with o( n) queries, using an argument based on a
recent proof by Alon and Blais [1].
Proof (Theorem 2). We begin by defining Pf . Formally, it is the set of graphs
satisfying the following conjunction of four clauses (see Figure 1(c) for an example).
∀x∃y∀z : { ((¬E(x, x) ∧ ¬E(z, z) ∧ x 6= z) → E(x, z))∧∧(E(x, x) → (E(x, y) ∧ ¬E(y, y) ∧ [(¬E(z, z) ∧ E(x, z)) → y = z]))(¬E(x, x) → (E(y, x) ∧ E(y, y) ∧ [(E(z, z) ∧ E(z, x)) → y = z]))∧((E(x, x) ∧ E(z, z)) → [¬E(y, y) ∧ E(x, y) ∧ (E(x, z) ↔ E(y, z))]) }A graph satisfies this formula if the following conditions are all satisfied.
1. The nodes without loops form a complete subgraph.
2. For every node x with a loop, there is exactly one y without a loop such that
there is an edge from x to y.
3. For every node y without a loop, there is exactly one x with a loop such that
there is an edge from x to y.
4. For all nodes x, z with loops, and y the unique node without a loop suchthat E(x, y), it holds that E(x, z) iff E(y, z).
Property P2 below is similar to Pf , except that the isomorphism is not explicitly given.
Definition 8. A graph G = (V, E) has P2 if it satisfies the following conditions.
1. There is a partition3 V1 , V2 ⊆ V such that |V1 | = |V2 |, there are loops(E(x, x)) on all x ∈ V1 and no loops (¬E(x, x)) for all x ∈ V2 .
2. The nodes without loops form a complete subgraph.
3. There are no edges from a node with a loop to a node without a loop.
3

V1 , V2 partition V if V1 ∩ V2 = ∅ and V1 ∪ V2 = V .

182

C. Jordan and T. Zeugmann

4. There exists a bijection b : V1 → V2 such that if x, z have loops, then E(x, z)
iff E(b(x), z).
It is not difficult to show that properties Pf and P2 are indistinguishable.
Claim 1 Properties Pf and P2 are indistinguishable.
Proof (Claim 1). Let ε > 0 be arbitrary and let Nε = ε−1 . Assume that G has
property P2 and that #(G) > Nε . We will show that mrdist(G, Pf ) < ε.
Graph G has P2 and so there is a bijection satisfying Condition 4 of Definition 8. We therefore add the edges E(i, b(i)) making the isomorphism (from V1
to V2 ) explicit. The resulting graph Gf has Pf .
We have made exactly n/2 modifications, all to non-loops, and n − 1 ≥ Nε ,so mrdist(G, Pf ) ≤ mrdist(G, Gf ) = 1/2(n − 1) < ε.
The converse is analogous; given a G that has Pf , simply remove the n/2
edges from loops to non-loops after using them to construct a suitable bijection b.
t Claim 1uProperties Pf and P2 are indistinguishable and so (by Theorem 1), it suffices
to show that P2 is is √untestable. Lemma 1 below is stronger than necessary, andactually implies a Ω( n) lower bound for testing Pf per the discussion following
Theorem 1.
t Theorem 2u√Lemma 1. Fix 0 < ε < 1/2. Any ε-tester for P2 must perform Ω( n) queries.
Proof (Lemma 1). The proof is via Yao’s Principle (cf. Principle 1), and so wedefine two distributions, Dno and Dyes and show that all deterministic testers
have an error-rate greater than 1/3 for property P2 when the input is chosenrandomly from Dno with probability 1/2 and from Dyes with probability 1/2.
In the following, we consider a distribution over graphs of sufficiently large
size 2n, and an arbitrary fixed partition of the vertices into V1 and V2 such that
|V1 | = |V2 | = n (for example, let the vertices be the integers V := [2n], V1 := [n]and V2 := V \V1 ).
We begin with Dno , defined as the following distribution.
1. Place a loop on each vertex in V1 and place no loops in V2 .
2. Place each possible edge (except loops) in V1 × V1 and V2 × V1 uniformly
and independently with probability 1/2.
That is, Dno is the uniform distribution of graphs (with this particular partition)satisfying the first three conditions of P2 .
Next, we define Dyes as the following.
1. Choose uniformly a random bijection π : V1 → V2 .
2. Place a loop on each vertex in V1 and place no loops in V2 .
3. For each possible edge (i, j 6= i) ∈ V1 × V1 , uniformly and independently
place both (i, j) and (π(i), j) with probability 1/2 (otherwise place neither ).
It is easy to see that Dyes generates only positive instances. Next, we showthat Dno generates negative instances with high probability.

Untestable Properties in the Kahr-Moore-Wang Class

183

Lemma 2. Fix 0 < ε < 1/2 and let n be sufficiently large. Then,
Pr

G∼Dno

[dist(G, P2 ) ≤ ε] = o(1) .

Proof (Lemma 2). Dno is the uniform distribution over graphs of size 2n with aparticular partition satisfying the first three conditions of P2 . Let Gε be the setof graphs G0 of size 2n satisfying these conditions and such that dist(G0 , P2 ) ≤ ε(regardless of partition).
Counting the number of such graphs shows|Gε | ≤

 
dε2n2 e 
X 2n2 2n n(n−1) H(ε)2n2
2n n(n−1)
2
n!
≤
2
n!2
,
i
n
n
i=0

where H(ε) := −ε log ε − (1 − ε) log(1 − ε) is the binary entropy function (cf.
Lemma 16.19 in Flum and Grohe [9] for the bound on the summation).
2
Distribution Dno produces each of 2n(n−1) 2n graphs with equal probability,
and so
 
2
2
|Gε |
2n
Pr [dist(G, P2 ) ≤ ε] ≤ n(n−1)+n2 ≤n!2H(ε)2n /2n
G∼Dno
n
2
4n n!2H(ε)2n
√
≈
πn2n2

2

= o(1) .

The approximation is asymptotically tight, which suffices.

t Lemma 2u

We have shown that Dyes generates only positive instances and that (with highprobability) Dno generates instances that are ε-far from P2 . Next, we show that(again, with high√ probability) the two distributions look the same to testers
making only o( n) queries.
The proof is similar to a proof by Alon and Blais [1]. We begin by defining
two random processes, Pno and Pyes , which answer queries from testers andgenerate instances according to Dno and Dyes , respectively.
Process Pno is defined in the following way.
1. Choose uniformly a random bijection π : V1 → V2 .
2. Intercept all queries from the tester and respond as follows.
(a) To queries E(i, i) with i ∈ V1 : respond 1.
(b) To queries E(i, i) with i ∈ V2 : respond 0.
(c) To queries E(i, j) with i ∈ V1 and j ∈ V2 : respond 0.
(d) To queries E(i, j) with i 6= j ∈ V1 : quit if we have queried E(π(i), j),otherwise respond 1 or 0 randomly with probability 1/2 in each case.
(e) To queries E(i, j) with i ∈ V2 and j ∈ V1 : quit if we have queriedE(π −1 (i), j), otherwise respond 1 or 0 randomly with probability 1/2 ineach case.
3. When the process has quit or the tester has finished its queries, complete
the generated instance in the following way. First, fix the edges that werequeried according to our answer. Next, place loops on each vertex in V1 , noloops in V2 and no edges from V1 to V2 . Place each remaining possible edge,
place it (uniformly, independently) with probability 1/2, ignoring π.

184

C. Jordan and T. Zeugmann

We define Pyes in the same way, except for the final step. When Pyes quits or
the tester finishes, it fixes the edges that were queried according to its answers,
and also fixes the corresponding edges (when relevant) according to π. Moreprecisely, for each fixed E(i, j) with i 6= j ∈ V1 , we also fix E(π(i), j) and for
fixed E(i, j) with i ∈ V2 , j ∈ V1 , we also fix E(π −1 (i), j), in both cases the sameas our response to E(i, j) (not randomly). The remaining edges are placed asin Pno .
Note that Pno generates instances according to Dno and Pyes generates
instances according to Dyes . In addition, Pyes and Pno behave identically until
they quit or answer all queries. In particular, if a tester does not cause theprocess to quit, the distribution of responses of its queries is identical for√thetwo processes. We show that, with high probability, a tester that makes o( n)queries does not cause either process to quit.
√
Lemma 3. Let T be a deterministic tester which makes o( n) queries, and let
T interact with Pyes or Pno . In both cases,
Pr [T causes the process to quit] = o(1) .
Proof (Lemma 3). The condition causing the process to quit is identical in Pyes
and Pno . The probability that any pair of queries E(i, j) and E(i0 , j 0 ) cause theprocess to quit is at mostPr [i0 = π(i) or i = π(i0 )] ≤(n − 1)!
= 1/n .
n!

√
The tester makes at most o( n) queries and so√
Pr [T causes the process to quit] ≤ o( n)2 O(1/n) = o(1) .
t Lemma 3u√
Any deterministic tester T which makes o( n) queries can only distinguishbetween Dyes and Dno with probability o(1), but it must accept Dyes withprobability 2/3, and reject Dno with probability 2/3−o(1). It is impossible for T
to satisfy both conditions, and the lemma follows from Principle 1. ut Lemma 1

4Conclusion

Property testing is a kind of randomized approximation, where we take a small,random sample of a structure and seek to determine whether the structure has adesired property or is far from having the property. We focused on the classification problem for testability, wherein we seek to determine exactly which prefix
vocabulary classes are testable and which are not. The main result of this paper
is the untestability of [∀∃∀, (0, 1)]= , a sharpening of the results of [14]. This classis a minimal class for untestability.
As mentioned in Subsection 1.1, the current classification for testability
closely resembles several other classifications (e.g., those for the finite modelUntestable Properties in the Kahr-Moore-Wang Class

185

property, docility and associated second-order 0-1 laws) and it would be interesting to determine whether it coincides with one of these. In particular,
determining the testability of variants of the Gödel class would complete theclassification for the special case of predicate logic with equality.

References[1] Alon, N., Blais, E.: Testing Boolean function isomorphism. In: Approximation,
Randomization, and Combinatorial Optimization, Algorithms and Techniques,
13th International Workshop, APPROX 2010, and 14th International Workshop,
RANDOM 2010, Barcelona, Spain, September 2010, Proceedings. Volume 6302 of
Lecture Notes in Computer Science., Springer (2010) 394–405[2] Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large
graphs. Combinatorica 20(4) (2000) 451–476[3] 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[4] Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications tonumerical problems. J. of Comput. Syst. Sci. 47(3) (1993) 549–595[5] Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. SpringerVerlag (1997)[6] Büchi, J.R.: Weak second-order arithmetic and finite-automata. Z. Math. Logik
Grundlagen Math. 6 (1960) 66–92[7] Fischer, E.: The art of uninformed decisions. Bulletin of the European Association for Theoretical Computer Science 75 (October 2001) 97–126 Columns:
Computational Complexity.
[8] Fischer, E., Matsliah, A.: Testing graph isomorphism. SIAM J. Comput. 38(1)(2008) 207–225[9] Flum, J., Grohe, M.: Parametrized Complexity Theory. Springer (2006)[10] Goldreich, O.: Introduction to testing graph properties. Technical Report TR10082, Electronic Colloquium on Computational Complexity (ECCC) (May 2010)[11] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection tolearning and approximation. J. ACM 45(4) (1998) 653–750[12] Jordan, C., Zeugmann, T.: Relational properties expressible with one universal
quantifier are testable. In Watanabe, O., Zeugmann, T., eds.: Stochastic Algorithms: Foundations and Applications, 5th International Symposium, SAGA
2009, Sapporo, Japan, October 2009, Proceedings. Volume 5792 of Lecture Notes
in Computer Science., Springer (2009) 141–155[13] Jordan, C., Zeugmann, T.: A note on the testability of Ramsey’s class. In Kratochvı́l, J., Li, A., Fiala, J., Kolman, P., eds.: Theory and Applications of Models ofComputation, 7th International Conference, TAMC 2010, Prague, Czech Republic, June 2010, Proceedings. Volume 6108 of Lecture Notes in Computer Science.,
Springer (2010) 296–307[14] Jordan, C., Zeugmann, T.: Untestable properties expressible with four first-order
quantifiers. In Dediu, A.H., Fernau, H., Martı́n-Vide, C., eds.: Language andAutomata Theory and Applications, 4th International Conference, LATA 2010,
Trier, Germany, May 2010, Proceedings. Volume 6031 of Lecture Notes in Computer Science., Springer (2010) 333–343[15] Kahr, A.S., Moore, E.F., Wang, H.: Entscheidungsproblem reduced to the ∀∃∀case. Proc. Nat. Acad. Sci. U.S.A. 48 (1962) 365–377

186

C. Jordan and T. Zeugmann[16] Kolaitis, P.G., Vardi, M.Y.: 0-1 laws for fragments of existential second-orderlogic: A survey. In Nielsen, M., Rovan, B., eds.: Mathematical Foundations ofComputer Science 2000, 25th International Symposium, MFCS 2000, Bratislava,
Slovakia, August/September 2000, Proceedings. Volume 1893 of Lecture Notes in
Computer Science., Springer (2000) 84–98[17] McNaughton, R., Papert, S.: Counter-Free Automata. M.I.T. Press (1971)[18] 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[19] Ron, D.: Property testing: A learning theory perspective. Found. Trends Mach.
Learn. 1(3) (2008) 307–402[20] Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends
Theor. Comput. Sci. 5(2) (2009) 73–205[21] Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2) (1996) 252–271[22] Vedø, A.: Asymptotic probabilities for second-order existential Kahr-Moore-Wang
sentences. J. Symbolic Logic 62(1) (March 1997) 304–319[23] Yao, A.C.C.: Probabilistic computations: Toward a unified measure of complexity. In: 18th Annual Symposium on Foundations of Computer Science, IEEE
Computer Society (1977) 222–227