TCS -TR-B-09-6

TCS Technical Report

Master's Thesis: The Classication Problem in
Relational Property TestingbyCharles Harold Jordan

Division of Computer Science
Report Series B
April 27, 2009

Hokkaido University
Graduate School ofInformation Science and Technology

Email: skip@ist.hokudai.ac.jp

Phone: +81-011-706-7675
Fax: +81-011-706-7675

The Classication Problem in Relational Property Testing
Charles Harold Jordan
Division of Computer Science, Graduate School of Information Science and Technology
Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan

Summary
In property testing, we desire to distinguish between objects that have a given property
and objects that are far from the property by examining only a small, randomly selected
portion of the objects. Property testing arose in the study of formal verication, however
much of the recent work has been focused on testing graph properties.
In this thesis we introduce a generalization of property testing which we call relational property testing. Because property testers examine only a very small portion of
their inputs, there are potential applications to eciently testing properties of massive structures. Relational databases provide perhaps the most obvious example of suchmassive structures, and our framework is a natural way to characterize this problem.
We introduce a number of variations of our generalization and prove the relationships
between them.
The second major topic of this thesis is the classication problem for testability. Using the general framework developed in previous chapters, we consider the testability ofvarious syntactic fragments of rst-order logic. This problem is inspired by the classical problem for decidability. We compare the current classication for testability withearly results in the classication for testability, and then prove an additional class to be
testable.

iContents
1
1.1
1.2

2

1

History of Property Testing . . . . . . . . . . . . . . . . . . . . . . . . . .
Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
2Preliminaries

4

2.1
2.2
2.3
2.4

Basic Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Property Testing Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Logical Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Classication Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Basic Results

14

3.1
3.2

Testable Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Untestable Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Yao's Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 An Untestable Property . . . . . . . . . . . . . . . . . . . . . . . .
Closure Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Indistinguishability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Testable Properties that are Hard to Decide . . . . . . . . . . . . . . . . .
Uniformity Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Alternate Denitions of Distance . . . . . . . . . . . . . . . . . . . . . . .

14
15
15
18
21
23
26
27
29

The Classication Problem for Testability

35

History of the Classication Problem . . . . . . . . . . . . . . . . . . . . .
4.1.1 Gurevich's Classiability Theorem . . . . . . . . . . . . . . . . . .
4.1.2 Classication Similarities . . . . . . . . . . . . . . . . . . . . . . .
Testability of Monadic First-Order Logic . . . . . . . . . . . . . . . . . . .
4.2.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Monadic First-Order Logic is Regular . . . . . . . . . . . . . . . .
Ackermann's Class with Equality . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Testability of Ackermann's Class with Equality . . . . . . . . . . .

35
36
36
38
38
39
43
43

Conclusion

48

3

3.3
3.4
3.5
3.6
3.7

4
4.1

4.2

4.3

5

Introductioni1

Chapter 1

Introduction
Property testing is an application of induction. Given a large object, for example agraph or database, we wish to state some conclusion about the entire structure after
examining only a small, randomly selected sample. Lovász [31] has described it as thethird reincarnation of this approach, after statistics and machine learning.
Property testers, which we formally dene in Chapter 2, are probabilistic approximation algorithms that examine only a small part of their input. Our goal is always todistinguish inputs that have some desired property from inputs that are far from having
it. We are especially interested in classication, i.e., considering the testability of large
classes of properties.
There is an enormous amount of recent work in property testing. In the following
section we introduce the history of the eld, focusing particularly on results that inuence
our approach. Then, in Section 1.2 we summarize the results and structure of this thesis.

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 [15] or Ron [39].
Property testing is a form of approximation where we trade accuracy for eciency.
Probabilistic machines appear to have been rst formalized by de Leeuw et al. [30], whoshowed that such machines cannot compute deterministically uncomputable properties
under reasonable assumptions. However, they explicitly mention the possibility thatprobabilistic machines could be more ecient than deterministic machines. An earlyexample of such a result is the matrix multiplication checker of Freivalds [17].
Property testing itself is generally considered to have arisen from program verication(see Blum et al. [10] and Rubinfeld and Sudan [40]). Here we have some program P (x)that purports to compute a function f (x) and we wish to quickly verify that P is correctwith high probability. Rubinfeld and Sudan [40] dene the distance between two functions
with the same domain and arity to be the fraction of the domain that they assign dierent
outputs. They then dene a tester for a set of functions to be a program that accepts
1

1.2.

THESIS OVERVIEW

2

P if P is a program for some f in the set and rejects P with high probability if P is far
from being a program for all f in the set.
We can consider a graph to be represented by a binary function e(x, y) that is 1 if
there is an edge from x to y and 0 otherwise, which is essentially an adjacency matrix.
Then, any set of such functions is a graph property, allowing us to consider testable anduntestable graph properties. This approach was rst considered by Goldreich et al. [20],where they show the existence of testable NP-complete properties among many otherresults. However, if we are interested in properties of bounded-degree graphs, the adjacency matrix encoding is wasteful. A related approach using incidence lists to represent
bounded-degree graphs has been studied by Goldreich and Ron [19]. Parnas and Ron [36]generalized this approach and attempted to move away from the functional representationof structures.
It is possible to consider properties of other structures, such as strings. Alon et al. [4]showed that although all regular languages are testable, there exist untestable contextfree languages (see Theorem 4 below). Chockler and Kupferman [13] extended the positive result to the ω -regular languages. However, much of the recent work has been
focused on graph property testing. Alon and Shapira [6] have written a survey of someof the recent results in graph testing.
If we consider graph property testing, Alon et al. [2] took the rst step towards a
logical characterization of the testable properties. They showed that all graph properties
expressible by rst-order sentences of the form  ∃∀ are testable and that there exists
a property expressible in the form  ∀∃ that is not testable. This leads naturally tothe classication problem for testability, which we consider in Chapter 4. Their positive
result was obtained by showing that all such properties are essentially instances of acolorability problem, all of which they then showed to be testable. Fischer [16] showedvarious generalizations of this kind of colorability problem to also be testable.
Later, Alon and Shapira [5] gave a (near) characterization of the graph properties
testable with one-sided error by algorithms unaware of the input size, a result that was
generalized to hypergraphs by Rödl and Schacht [38]. Alon et al. [3] obtained an exact
combinatorial characterization of the graph properties testable with a constant numberof queries.

1.2 Thesis Overview
In this thesis we particularly focus on two issues in property testing. First, much of therecent work in testing has been focused on graph properties. In contrast, we seek a moregeneral framework, which we call relational property testing. We introduce denitions
and notation in Chapter 2 and then show a number of basic results in Chapter 3.
There are several possible variations of our framework. We prove the relationships
between several such variations in Section 3.7. It is also possible to consider applicationsof property testing. In particular, we could be interested in eciently testing properties
2

1.2.

THESIS OVERVIEW

3

of massive structures such as relational databases, a problem which is characterized by
our framework. Properties of databases are generally dened in formal query languages
such as SQL and so it is natural to consider the testability of such languages.
The second major topic in this thesis is the classication problem for testability, which
we consider in Chapter 4. The objective here is to provide a classication of exactly
which classes of rst-order logic are entirely testable and which classes are not, which we
consider in the framework of relational property testing developed in earlier chapters. We
provide an overview of the currently known results for this classication and comparethem with the classical results in the classication for decidability. We also show thetestability of Ackermann's class with equality, providing an additional parallel to theclassical case.

3

4

Chapter 2

Preliminaries
The notations and denitions that we require are divided into several topics. We consider property testing in a very general setting instead of restricting ourselves to someparticular type of structure such as graphs.
In order to discuss properties of graphs or of strings, it is necessary to rst denethese types of structures. We therefore dene fundamental notions such as vocabularies(types of structures) and structures in Section 2.1. This provides a sucient basis toformalize our denitions of property testing, which we do in Section 2.2. This thesis
is particularly focused on questions of formal logic in property testing, and so we givedenitions related to logic in Section 2.3 and those used for discussing the classication
problem in Section 2.4.
Before proceeding further, we recall fundamental denitions and introduce notation forfamiliar objects such as natural numbers, sets and strings. Our denitions are standard
and readers familiar with this material can safely skip to Section 2.1.
The natural numbers are denoted by N and are the set of non-negative integers. We
denote the set of real numbers by R, although these are generally used for probabilities
and so we usually use only real numbers p ∈ [0, 1]. We use bold characters to denote
vectors, for example x ∈ R3 . Vectors are row vectors unless otherwise noted, we denotethe transpose of a vector by xT . If x = (x1 , . . . , xa ) is a vector, we call xi the i-thcomponent of x.
The empty set is denoted by ∅. If A and B are sets, then the union of A and B is
A ∪ B := {x | x ∈ A or x ∈ B}, the intersection of A and B is A ∩ B := {x | x ∈A and x ∈ B}, and the set dierence of A and B is A\B := {x | x ∈ A and x 6∈ B}.
∪
We generalize the union and intersection in the usual way, i≥0 Ai := A0 ∪ A1 ∪ . . . and∩i≥0 Ai := A0 ∩ A1 ∩ . . . respectively.
Set A is a subset of set B , written A ⊆ B if A\B = ∅. Set A is a proper subset of set
B , written A ⊂ B if A ⊆ B and B\A 6= ∅. The cardinality of a set A is the number of
elements in the set, written |A|.
The product of sets A and B is the set of ordered pairs, A × B := {(a, b) | a ∈A and b ∈ B}. The set of n-tuples of set A, written An is dened inductively as follows.

4

2.1.

5

BASIC DEFINITIONSFirst, A1 = A. Then, An+1 = An × A. We will always omit the extra parentheses,
and so (1, 2, 3) denotes ((1, 2), 3). The number of elements in the tuple is the arity n.
A predicate P with arity n of set A is any subset of An . If x ∈ An , we will generally
abbreviate the proposition x ∈ P with P (x).
An alphabet Σ is a set of symbols, and a string w over Σ is some sequence of thesymbols in Σ. The empty string is denoted by λ. For example, {0, 1} is the alphabetof binary strings and 0100 is an example of such a string. We number the positions ina string w from left to right with 0, 1, . . . , n − 1 where n is the length of the string. Of
course, the empty string λ has length 0. As usual, Σ∗ is the free monoid of Σ and any
subset L ⊆ Σ∗ of it is a language.
Let w be a string over the alphabet Σ. The concatenation of strings u and v is uv ,while the product of two sets of strings L1 and L2 is L1 L2 := {uv | u ∈ L1 and v ∈ L2 }.
←←The reversal of w is written w. Position i of w corresponds to position n − 1 − i of w.
←←←
Formally, λ = λ and aw = wa for a ∈ Σ.
We mention a number of well-known classes of languages, for example the classes of regular and context-free languages. Hopcroft and Ullman [26] is a well-known introduction
to these classes.
It is natural to represent a binary string w ∈ {0, 1}∗ as a pair {U, S} where U is thenite set of bit positions 0, . . . , n − 11 and S ⊆ A is a monadic predicate. We will deneS(i) to mean that bit position i of w is 1.
Graphs provide another natural example and allow for representation as a pair, (V, E).
Here V is the set of vertices and the edge set E ⊆ V 2 , a set of ordered pairs of V . The
names of the vertices are not interesting to us, and we will identify them as 0, . . . , n − 1
where n is the number of vertices. It is therefore natural to represent a graph as a pair{V, E} where E is a binary predicate over V .
We will formalize these notions more exactly in the following section. In particular,
one of our goals is a generalized notion of property testing instead of restricting ourselvesto xed kinds of structures such as graphs and binary strings. The denitions in thefollowing section are therefore necessarily abstractions of the ideas above.

2.1 Basic Denitions
Instead of restricting our attention to, for example, graphs, we focus on property testingin a general setting. We begin by dening vocabularies, which will also be the basis formost of our logical denitions. A predicate symbol is simply a syntactic character which
is used to refer to predicates. Likewise, the arities in the following denition are simply
positive integers that are later interpreted as arities.

Denition 1. A vocabulary τ is a tuple of distinct predicate symbols Ri together with
their arities ai ,

τ := (R1a1 , . . . , Rsas ).
1

The universe is the empty set if w is the empty string.

5

2.1.

6

BASIC DEFINITIONSWhen we prove general theorems for all vocabularies, we will always use vocabularies τ
as in Denition 1. The predicate symbols in these theorems will therefore always be
named Ri for 1 ≤ i ≤ s and have arities ai . Two examples of vocabularies are τG := {E 2 },the vocabulary of directed graphs and τS := {S 1 }, the vocabulary of binary strings.
In order to dene structures we must consider universes, which are sets. Our universes
are always nite and we generally refer to the cardinality of a universe with n.

Denition 2. An (algebraic) structure A of type τ is an (s + 1)-tupleA
A := (U, RA
1 , . . . , Rs )Aaconsisting of a nite universe U and where each Ri ⊆ U i is a predicate corresponding
to the predicate symbol Ri .

In the following, we omit (algebraic) and refer to such structures simply as structures.
We also omit the vocabulary when it is understood. If the universe U is the empty set,
then n = 0 and the structure is the unique empty structure of type τ . Such structures
are not very interesting in terms of testing but it is worth noting their existence.
For convenience we will always identify the elements of U with the non-negative integers{0, . . . , n − 1} and use n = #(A) for the size of the universe of a structure A. As anotational convenience, we will use Un := {0, 1, . . . , n − 1} to refer to the universe of nelements. We use calligraphic characters to denote the predicates dened by a structure,
however our logical denitions will provide a more convenient way (using the predicate
symbols) to state propositions regarding the predicates.
If we consider a binary string, the universe U is the set of bit positions, which we will
identify as {0, . . . , n − 1} from left to right. For i ∈ U , we interpret the meaning of i ∈ S
as bit i of the string is 1. Likewise, for a graph G, the universe is the set of vertices,which we again identify as {0, . . . , n − 1}. For x, y ∈ U , we interpret (x, y) ∈ E as there
is an edge from x to y in the graph. Our graphs are therefore directed and possibly
contain loops.
We dene STRUC n (τ ) to be the set of all structures with vocabulary τ and universe∪
size n. We then dene STRUC (τ ) := 0≤n STRUC n (τ ) to be the set of all structuresof type τ .
A property P of structures of type τ is a set of structures of type τ , and so P ⊆STRUC (τ ). We do not consider properties of structures of mixed types, although it
would be possible to do so. For all A ∈ P , we say that structure A has property P .
That is, in order to avoid unwieldy language, having a property is always dened as
membership in the set of structures dening the property. To reect the conventionalterminology from formal language theory, we use language instead of property to referto sets of strings.
An example of a property is that of being a binary palindrome. A binary string is apalindrome if it is equivalent to its reversal. The language of such binary strings can bedened as

LP := {w | w ∈ STRUC (τS ) and | ∀i ∈ U : i ∈ S i (#(w) − 1 − i) ∈ S}.
6

2.2.

PROPERTY TESTING DEFINITIONS

7

We generally use L, P and Q to denote properties and A and B to refer to structures.
However, we refer to strings as u,v and w to reect more common notation.

2.2 Property Testing Denitions
In property testing we wish to distinguish, with high probability, between inputs thathave some desired property and inputs that are far from having the property. We begin
by dening a distance measure between structures. The symbol ⊕ denotes exclusive-or.
We recall that vocabulary τ = {R1a1 , . . . , Rsas } and that the universe of a structure isdenoted by U (cf. Denition 1).

Denition 3. Let A, B ∈ STRUC (τ ) be structures such that #(A) = #(B) = n. The
distance between structures A and B is∑ai and RA (x) ⊕ RB (x)}|ii1≤i≤s |{x | x ∈ U∑sdist(A, B) :=
.
ai
n
i=1
That is, the distance is dened as the number of tuples that are assigned dierent truth
values for the same predicate symbol in A and B , divided by the total number of tuples.
It is the fraction of assignments on which the two structures disagree. For structuresthat are binary strings, the above denition is equivalent to their edit distance.
In the case of graphs, Denition 3 is equivalent to the adjacency matrix model introduced by Goldreich et al. [20]. This approach is particularly suited to dense graphs, andan alternative approach for bounded degree graphs which are represented using bounded
incidence lists has been developed by Goldreich and Ron [19].

Denition 4. Let P be a property of structures with vocabulary τ and A be such astructure with a universe of size n. Then, A is said to be ε-far from P if every structure

B with universe of size n and vocabulary τ that has P satises dist(A, B) ≥ ε.
Structure A is far from having a property if it is far from all structures that have theproperty and are the same size as A. Our goal is to dierentiate between structures thathave a desired property and those that are far from having the property. As usual, we
must have this property in mind before constructing algorithms for it. We are especiallyinterested in extremely ecient probabilistic approximation algorithms that examine
only a very small portion of the structure.
Instead of directly providing these algorithms with the structures as input, we provide
them with access to an oracle. We will assume that the algorithm is for testing property
P of type τ , and that we wish to run this on the input A ∈ STRUC (τ ). The algorithm
is allowed to query the oracle for desired bits of the input. We formalize the queries as
being of the form Ri (x), where Ri is a predicate symbol in the vocabulary τ determinedby the property and x ∈ Nai is some tuple with the appropriate arity. The oracle thenreturns  1 if the tuple is in the predicate RA
i and  0 if it is not.

7

2.2.

PROPERTY TESTING DEFINITIONS

8

Once the structure A is xed, it is of some xed universe size n. A truly random queryis overwhelmingly likely to be of a tuple x 6∈ Un . It is therefore essential to provide
the algorithm with some means of making meaningful queries. In our model we allow
an additional, special query: The algorithm may ask the oracle for n, the size of theuniverse.
We discuss multiple variations of the above after formalizing our denition in thefollowing way. In particular, the special query for the universe is not allowed in theso-called oblivious model. There, it is common for the algorithm to give the oracle anatural number m, in response to which the oracle returns a uniformly random induced
substructure of A with size m or an error if no such substructure exists.

Denition 5. An ε-tester for property P is a randomized algorithm that is 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 A with probability at least 2/3 if A has

P and must reject A with probability at least 2/3 if A is ε-far from P .
The choice of 2/3 in Denition 5 is both traditional and arbitrary. Any probability
strictly greater than 1/2 can be chosen and the resulting testers iterated a constantnumber of times and the majority taken to achieve any desired accuracy strictly lessthan one, see e.g., Hromkovi£ [27]. The tester is not designed according to any particular
structure A and so dierent inputs can be tested using dierent oracles. However, thetester may be designed using the approximation parameter ε, which we discuss shortly.
Our denition of testers allows them to know the size of the input, have two-sided error
and make adaptive queries based on the results of previous queries. Testers that are notgiven the size of their input are known as oblivious testers. These testers generally makequeries by requesting a random sample of the input which is of a certain size. Such asample is returned if it exists, otherwise the query fails. It is easy to construct properties
that are testable by our denition but not by oblivious testers; for example, the property
that the size of the universe is odd. In fact, several of the testers in this thesis will
examine the size of the universe.
Many of those testers will examine the size of the universe only to determine if it issuciently large, where suciently large is dened as greater than some function of ε. It
is possible to construct an oblivious tester in such cases, by having the tester request asample that is larger than this function. The input is suciently large i such a sample
is available.
Alon and Shapira [7] have provided an exact characterization of the graph properties
testable by oblivious testers with one-sided error. Goldreich and Trevisan [21] haveshown that every graph property testable with q adaptive queries can be tested withO(q 2 ) non-adaptive queries and Gonen and Ron [22] have shown that this gap exists.
We have mentioned above the notion of testable properties, and also implied the existence of untestable properties. It is therefore necessary to dene testability, which we do
as follows.
8

2.3.

LOGICAL DEFINITIONS

9

Denition 6. Property P is called testable if for every ε > 0 there exists an ε-testerthat makes a number of queries which can be upper-bounded by a function depending onlyon ε.

It is interesting to note we allow dierent ε-testers for each ε > 0 and natural to ask
why a single algorithm does not suce. The situation is similar to that familiar in circuit
complexity (cf. Straubing [45]), where we have uniform and non-uniform cases.
Denition 6 is non-uniform in the sense that the ε-testers may not be constructible
given ε. It is very natural to require the ε-testers for P to be computable given ε,an additional condition (equivalent to requiring the ε-testers to be a single algorithm)
that results in uniform testability. We [28] have shown that there exist undecidable
properties that are testable i we use a non-uniform denition of testability while Alonand Shapira [8] have also shown the same separation between uniform and non-uniform
testability using a decidable property. We discuss the role of uniformity in Section 3.6.
Alon and Shapira [8] also emphasize the importance of the function in Denition 6
being only an upper bound on the number of queries. This is because query complexities
such as 1/ε + (−1)n are acceptable, albeit problematic for oblivious testers.

2.3 Logical Denitions
The denitions in this section are used especially in formulating and discussing classication problems in Chapter 4. Our logic is a pure predicate logic with equality that does
not contain function symbols. There are no ordering symbols such as ≤ nor are there
arithmetic relations such as PLUS or BIT. Enderton [14] provides a more comprehensive introduction to logic and Börger et al. [11] is an excellent reference for classication
problems.
We begin by dening the underlying language. There exist countably innite variable
symbols, which we generally name with (possibly subscripted) x, y and z . We use lower
case letters to distinguish these variable symbols from predicate symbols and let V AR
be the set of variable symbols.
The equality symbol (=) is special. Although = is a predicate, we do not allow structures to redene it and insist that it is always interpreted as true equality. We do notallow function symbols or constant symbols (nullary function symbols).
Given a vocabulary τ as dened in Denition 1, the rst-order logic of τ is dened asfollows. Our logic does not contain constant symbols, and so the atomic terms are thevariable symbols, x. Our language does not contain function symbols, and so the terms
are exactly the atomic terms.
The atomic formulas are x = y for terms x and y and Ri (x1 , . . . , xai ) where the xj areterms and Ri is a predicate symbol of τ .
The formulas are dened inductively. If ϕ and ψ are formulas, then (ϕ ∨ ψ) and (¬ϕ)
are formulas. If x is a variable, then (∃x : ϕ) and (∀x : ϕ) are also formulas. A wellformed formula is a formula in which no variable occurs free. The rst-order logic of τ
9

2.3.

10

LOGICAL DEFINITIONS

is exactly the set of well-formed formulas. We have no further use for formulas with freevariables and will now refer to well-formed formulas simply as formulas.
Additional connectives including ∧, → and ↔ are allowed but are formally consideredabbreviations. The parentheses required by the denition are omitted where the intended
meaning is clear.
We say that a structure A of type τ and universe Un models (or satises) a formula ϕ,written A |= ϕ, if ϕ is true when interpreted in the context of A. We dene this moreformally in the following way.
An interpretation is a function from the variable symbols to the universe,

I : V AR 7→ Un .
In addition, the function f maps the predicate symbols of τ to their corresponding
predicates in A, that is, f (Ri ) = RA
i . Recalling that vocabularies and structures aretuples, the function f maps the i-th element of τ to the (i + 1)-th element of A.
As a notational convenience, if I is a function, we will write I[x\\a] to meanI(y), if y 6= x;I[x\\a](y) =a,if y = x.
That is, I[x\\a](y) is the function I(y) except that the value I(x) has been replacedwith a.
The denition of truth is inductive and follows our denition of formulas. We only
write A |= ϕ for well-formed formulas ϕ and so the initial interpretation is irrelevant,but formulas which are not well-formed may appear during the inductive steps. We saythat A |= ϕ if there is an interpretation I such that (A, I, f ) |= ϕ. Inductively,
1. (A, I, f ) |= (x = y) if I(x) = I(y). Note = is always interpreted as equality on Un ;2. (A, I, f ) |= Ri (x1 , . . . , xai ) if the tuple (I(x1 ), . . . , I(xai )) ∈ f (Ri );3. (A, I, f ) |= (ψ ∨ γ) if it is true that (A, I, f ) |= ψ or (A, I, f ) |= γ ;4. (A, I, f ) |= (¬ψ) if (A, I, f ) |= ψ is not true,
5. (A, I, f ) |= (∃x : ψ) if there exists an a ∈ Un such that (A, I[x\\a], f ) |= ψ ;6. (A, I, f ) |= (∀x : ψ) if for every a ∈ Un , it is true that (A, I[x\\a], f ) |= ψ .
This denition of truth is generally attributed to Tarski [47] (see [48] for an English
translation).
We say that formula ϕ denes property P := {A | A |= ϕ} and so A |= ϕ is equivalent
to saying that A has property P . On one hand, the expressive power of our language
is quite weak. First-order logic with ordering (≤) and arithmetic relations PLUS andTIMES, or equivalently BIT, is a characterization of DLOGTIME-uniform AC 0 , see e.g.
Barrington et al. [9]. It therefore cannot express the property PARITY, which is true
10

2.4.

CLASSIFICATION DEFINITIONS

11

only for binary strings containing an odd number of 1s, see Furst et al. [18]. Our language
does not contain ordering or arithmetic relations and so it is even weaker.
On the other hand, it is rich enough to express both testable and untestable properties.
In some sense (see indistinguishability in Section 3.4) it is more powerful in the context
of testing than classically. It is useful that our language is the same as the pure predicate
logic considered in the traditional classication problem, allowing us to make several
comparisons in Subsection 4.1.2. Finally, properties that are closed under isomorphisms
are most natural in property testing and many possible additions to our language would
force us to focus on properties that are not closed under isomorphisms.
We use lower-case Greek letters, especially ϕ, ψ and γ , for rst-order formulas andx, y and z for rst-order variables. We refer to members of the universes of structureswith a, b and u when it is necessary to distinguish between variables and the underlying
members of the universe that they are bound to.

2.4 Classication Denitions
Recall that every rst-order formula has an equivalent formula in prenex normal form.
That is, for any ϕ there exists a logically equivalent ϕ0 that is of the form

ϕ0 = π1 x1 . . . πa xa : ψ,
where ψ is quantier-free and the πi are either ∀ or ∃. For example, the rst-orderformula ∃x : (S(x) ∧ ∃x : (¬S(x))) is equivalent to ∃x∃y : (S(x) ∧ ¬S(y)).
This example can be expressed with two existential quantiers (∃2 ), a single monadic
predicate and does not require equality. There are a number of common ways to classify rst-order formulas, including the number of distinct variables and the number ofquantiers. However, the most traditional methods have been to classify formulas inprenex normal form based on the pattern of quantiers and the vocabulary τ dening
the language. In particular, there are a number of interesting relationships between thetestability of properties and the patterns of quantiers that can be used to express them.
Our denitions for classication are very similar to those used by Börger et al. [11],however one notable dierence is that we restrict ourselves to pure predicate logics rather
than also considering logics with function symbols. The similar notation allows us toeasily compare what is currently known regarding the classication for testability withthe traditional classication for decidability, which we do in Section 4.1.2.

Denition 7. A prex vocabulary class is specied as[Π, p]e .
∗ ∗Here, Π is a string over the four-character alphabet {∃, ∀, ∃ , ∀ }, p is either the special
phrase `all' or a sequence over N and the rst innite ordinal ω , and e is either `=' or λ.

11

2.4.

CLASSIFICATION DEFINITIONS

12

Note that we have only dened a syntactic object; it is essentially a triple that also
contains two brackets. In general, p is an innite sequence although we will consider
normal forms shortly. We will use these triples to dene classes of rst-order formulas,and so we now dene their meaning.
The rst-order sentence
ϕ := π1 x1 π2 x2 . . . πr xr : ψin prenex normal form, with quantiers πi and quantier-free ψ , is a member of the prex
vocabulary class given by [Π, (p1 , p2 , . . .)]e , where pi ∈ N ∪ {ω} i
1. The string π1 π2 . . . πr is contained in the language specied by Π when Π is interpreted as a regular expression2 .
2. If p is not all, at most pi distinct predicate symbols of arity i ≥ 1 appear in ψ .
3. Equality (=) appears in ψ only if e is `='.
That is, Π describes the pattern of quantiers for sentences in the class, p gives the
maximum number of predicate symbols of each arity and e determines whether the equality symbol is permitted. It is traditional to include an additional sequence f describing
the permitted function symbols, but we do not allow function symbols and so omit f .
Our sentences are always nite in length. If a prex class has pi = ω , then formulas
may contain any nite number of i-ary relation symbols. If p = all, then formulas in theclass may contain any nite number of relation symbols of any nite arities.
We mentioned above that p is, in general, an innite sequence. However if we consider graphs as an example, it is tiresome to write the innitely many trailing zeros in(0, 1, 0, . . .). As a convention, we therefore suppress trailing zeros in p, and so (0, 1)
corresponds to the case of graphs.
If there are not innitely many trailing zeros in p, then the sum pi + pi+1 + · · · isinnite for all i. In this case, we can use some of these higher arity predicate symbols tosimulate lower arity symbols, for example using E(x, x) to simulate a monadic predicate
S(x). This implies that all sequences p have an equivalent sequence p0 such that p0 iseither a nite sequence (omitting trailing zeros) or the special phrase all. This is part ofthe denition of a standard prex class, see Börger et al. [11].
We are interested in the testability of prex classes and so we say that a prex class is
testable if every formula in the class expresses a testable property in the context of every
vocabulary in which it is possible to evaluate the formula. However, it is sucient toconsider only the minimal vocabulary needed to evaluate the formula. We formalize thisin the following simple lemma, where an extension of a vocabulary τ is any vocabulary
formed by adding a new (distinct) predicate symbol to those in τ .

2

We slightly modify the usual semantics of regular expressions so that ∀ (resp. ∃) matches the empty

string λ as well as ∀ (resp. ∃). This is because we wish to consider closed prex vocabulary classes, see
Section 2.3.3 of Börger et al. [11].

12

2.4.

CLASSIFICATION DEFINITIONS

13

Lemma 1. Let ϕ be a formula in the rst-order logic of vocabulary τ and τ 0 be any
extension of τ .

If ϕ denes a property that is testable in the context of τ , then the
0 dened by ϕ is also testable.

property of type τ

Assume ϕ denes property P of type τ when interpreted as a formula of type τand property P 0 of type τ 0 when interpreted as a formula of type τ 0 . Additionally assume
that the new predicate symbol in τ 0 is N which has arity a.
Let Tετ be a ε-tester for P . We will show that this is also a ε-tester for P 0 . Let A be a
structure with type τ 0 and assume A ∈ P 0 . Removing the N predicate, the correspondingA0 ∈ STRUC (τ ) has property P and so the tester will accept with probability at least
2/3, as desired.
Assume that dist(A, P 0 ) ≥ ε and again let A0 be the structure of type τ formed byremoving the N predicate from A. By the denition of distance,∑
ai and RA (x) ⊕ RB (x)}|ii1≤i≤s |{x | x ∈ U
0∑sdist(A , P ) = min
≥
ai
B∈P
n
i=1

Proof.

∑
dist(A, P 0 ) = minB∈Pai and RA (x) ⊕ RB (x)}|ii1≤i≤s |{x | x ∈ U
∑s
≥ ε.
a
a
i
n + i=1 n

The tester will therefore reject such A with probability at least 2/3 as desired.
Testable properties therefore remain testable when the vocabulary is extended and soa property is testable in every relevant vocabulary if and only if it is testable in theminimal relevant vocabulary. A prex class is untestable if it is not testable, that is, if it
includes some property that is untestable.

13

14

Chapter 3

Basic Results
3.1 Testable Properties
Perhaps the most basic result in property testing is the existence of the objects being
studied, testable properties. The testability of a property depends only on the property
itself and not on which of the various equivalent denitions (formulas) expresses it. It
is therefore easy to see that trivial properties such as always true and always false aretestable, but it is worthwhile to prove an example explicitly. We begin by considering
palindromes of even length. It is easy to extend this to all palindromes, however it isuseful to maintain uniformity with later results (cf. Theorem 4) from the literature.

Theorem 1. The property of being an even-length palindrome, LP = {u←u} over thealphabet {0, 1}, is testable with query complexity O(1/ε).
Proof.

The following algorithm is an ε-tester for the property.

1. Query the oracle for the number of characters, n. Reject if n is odd.
2. Choose 2/ε integers uniformly at random from [0, n/2 − 1].
3. For each of these integers i, query the oracle for S(i) and S(n − 1 − i).
4. Reject if any of these pairs dier, otherwise accept.
To show that this is an ε-tester for even-length palindromes, we are required to showthat it accepts palindromes with probability greater than 2/3, and rejects when the oracle
uses a string w where dist(w, LP ) ≥ ε, again with probability greater than 2/3. The rstpart is easy; if the input is a palindrome, the bits we compare will be equal by denitionand so we will accept with zero error.
Next, assume that dist(w, LP ) ≥ ε. Therefore, there are at least εn bits in w that must
be modied to reach a palindrome. For each of the random bit pairs that we examine,the probability that we have failed to nd one of these bits of evidence is at most (1 − ε).
The total error probability is then at most (1 − ε)2/ε , which is uniformly upper-boundedby e−2ε/ε = e−2 ≈ 0.135 for all ε in (0, 1], where e is the Euler number. The tester
therefore rejects such inputs with probability at least 1 − e−2 > 2/3, as desired.
14

3.2.

UNTESTABLE PROPERTIES

15

The language of palindromes (with even length) is a well-known example of a contextfree language that is not regular. The property of being an empty graph is also testable,
and the proof is nearly identical. However, we will use both results a number of times,
and so we show both explicitly.

Theorem 2. The property of being an empty graph,
PE := {G | G ∈ STRUC (τG ) and G has no edges},is testable.
Proof.

The following is an ε-tester for the property.

1. Query the oracle for the number of vertices, n.
2. Choose 2/ε pairs of vertices (x, y) uniformly at random.
3. For each of these pairs, query the oracle for E(x, y).
4. Reject if we see any edges, otherwise accept.
Of course, we will not see any edges if the input is empty and so we will accept withzero error. For G such that dist(G, PE ) ≥ ε, graph G contains at least εn2 edges. For
each of the random pairs that we query, the probability that we have failed to nd anedge is at at most (1 − ε). As above, the total error probability is at most (1 − ε)2/ε
which is strictly less than 1/3 for all ε ∈ (0, 1]. Therefore, we will nd an edge and rejectsuch G with probability at least 2/3, as desired.

3.2 Untestable Properties
In Section 3.1, we proved that the language of (even-length) palindromes is testable byproviding a correct tester that makes O(1/ε) queries. Here we wish to show that there
exists an untestable property, i.e., a property which cannot be tested with o(n) queries.
The example and proof that we use is due to Alon et al. [4].
The specic example given here allows a number of interesting corollaries, for example,
that the testable properties are not closed under complement (Corollary 3). We begin
by reviewing and proving the tool that we will use to prove non-testability.

3.2.1 Yao's Principle
The proof relies on a variation (Principle 1) of Yao's principle, a tool for proving lower
bounds in the context of randomized algorithms. Yao's principle is an interpretation
by Yao [49] of von Neumann's [34] minimax theorem for randomized computation. We
prove only the direction of the minimax theorem that is required for our purposes; for asurvey of minimax theorems and their proofs see Simons [42].
We begin by providing the denitions required to state Principle 1.
15

3.2.

16

UNTESTABLE PROPERTIES

Denition 8. A deterministic tester is a binary tree where each internal node is labeledwith a non-negative integer, each leaf is labeled accept or reject, and the two edges
from a node are labeled 0 and 1.

Given an input, we execute the tester as follows. Beginning at the root, we interpretthe labels on internal nodes as the bit position of the input that will be queried. If theresult of the query is 0, we follow the 0 edge and otherwise the 1 edge. When we reach aleaf we output the decision on the label. Note that it is equivalent to label the internal
nodes with atomic formulas such as E(0, 1) as these are equivalent to specic bits of the
input, the positions of which can be easily computed.

Denition 9. The complexity of a deterministic tester is the number of internal nodes,
including the root unless it is a leaf, on the longest path from the root to a leaf.

The complexity of a deterministic tester is then the maximum number of queries thatit makes. Our interest is limited to testers of nite complexity, i.e., those that output
a decision in nite time. Without loss of generality, we can restrict our attention tobalanced binary trees, by making extra, useless queries on the shorter paths in order topad their lengths.

Principle 1 (Yao's Principle). Let τ be a vocabulary. If there exists an ε ∈ (0, 1) and an(τ ) such that all deterministic testers with complexity c havean error-rate greater than 1/3 for property P , then P is not testable with complexity c.
distribution over STRUC

The denition of testable is of course our usual one involving random testers. In
general, our goal will be to show that it is impossible to test P using randomized testers
whose complexity does not depend on the input size. That is, for suciently large n andsome increasing function c := c(n) of n, we wish to nd a distribution of inputs suchthat all deterministic testers with complexity c have error-rates greater than 1/3.
For testability, we are concerned only with the error-rate on inputs that either have ourdesired property or are ε-far from having the property. Therefore, we dene the error-rate
of a tester to be non-zero only on such examples. Because of this, it suces to restrict ourattention to distributions that give zero probability to the remaining possible inputs(those that do not have the property in question, but are also not ε-far from it).
We begin by proving the following direction of the minimax theorem. We say that avector x ∈ R|x| is a probability vector if each of its components is a non-negative real
number and the sum of its components is 1. For n > 0, we let Pn be the set of probability
vectors with n components,{}n∑
Pn := x | x = (x1 , . . . , xn ) ∈ Rn , xi ≥ 0 for all 1 ≤ i ≤ n, andxi = 1 .
i=1

It is well-known that equality holds in the following, however we restrict ourselves tostating and proving only the direction required for Principle 1, as mentioned above.
16

3.2.

17

UNTESTABLE PROPERTIES

Theorem 3 (Minimax Theorem). Let M be an a × b matrix of non-negative reals and
X = Pa and Y = Pb be the sets of all probability vectors with a and b components,
respectively. Then,max min xM yT ≤ min max xM yT .
y∈Y x∈X

Proof.

(3.1)

x∈X y∈Y

Let y∗ be any of the arg max on the left in (3.1),y∗ := arg max min xM yT ,
y∈Y

x∈X

and x∗ be any of the arg min on the left in (3.1),x∗ := arg min xM y∗ T .
x∈X

Then, for any probability vector x ∈ X , by the denition of minimum,xM y∗ T ≥ x∗ M y∗ T .

(3.2)

Let x+ and y+ be any of the arg min and arg max on the right of (3.1), that is

x+ := arg min max xM yT and y+ := arg max x+ M yT .
x∈X

y∈Y

y∈Y

Then, by the denition of maximum, x+ M y+ ≥ x+ M y∗ T . Therefore, by (3.2),
T

min max xM yT = x+ M y+ ≥ x+ M y∗ T ≥ x∗ M y∗ T = max min xM yT .
Tx∈X y∈Yy∈Y x∈X

Given Theorem 3, it is easy to show Principle 1. In (3.1), we call x on the left and yon the right inner vectors. This is because we can think of them as being chosen afterthe outer vectors (y on the left and x on the right) are xed. For the inner vectors, itsuces to consider unit vectors ei , where component i is 1 and all other elements are 0.
This is because once the outer vector is xed, denoting the i-th component of a vector z
by [z]i ,min xM yT = earg mini [M yT ]i M yTx∈X

and likewise for the maximum on the right of (3.1). This proves the following simple
corollary of Theorem 3.

Corollary 1. Let M be an a × b matrix of non-negative reals and X = Pa and Y = Pb
be the sets of all probability vectors with a and b components, respectively. Then,max min ei M yT ≤ min max xM eTj .
y∈Y ei ∈Xx∈X ej ∈Y

(3.3)

17

3.2.

UNTESTABLE PROPERTIES

18

Proof (Principle 1). Principle 1 is an interpretation of (3.3) in the context of testing. We

let a be the number of deterministic testers with complexity c whose queries are evaluable
in structures of type τ that have n elements. We assume that there is an enumeration ofthese testers. Then, a randomized tester with complexity c for structures of n elements
is given by a probability vector x ∈ X , where [x]i is interpreted as the probability thatthe randomized tester behaves like the i-th deterministic tester. A unit vector ei ∈ X
species the i-th deterministic tester.
Likewise, we assume there is an enumeration of structures of type τ that have nelements and let b be the number of such structures. Then, a probability vector y ∈ Y
is a distribution over these structures and a unit vector ej species the j -th structure.
For matrix M , we let Mij be 1 if the i-th deterministic tester is incorrect on the j -th
input and this input either has the desired property or is ε-far from it. Otherwise, we let
Mij be 0.
We now have have an a×b matrix M and a meaning for a and b component probability
vectors and so we can interpret the meaning of Corollary 1. On the left, ei M yT is
the average-error of the i-th deterministic tester on a structure chosen according to
distribution y. Likewise, on the right, xM eTj is the error-rate of the randomized tester
specied by x on the j -th structure.
Therefore, the left side of (3.3) is the average-error of the best deterministic tester onthe worst distribution of inputs, when we dene best as the lowest average-error. If
we nd some distribution y+ of inputs such that all deterministic testers have an errorrate greater than 1/3, then 1/3 is a lower bound on the left side, and therefore the rightside, of (3.3).
The right side of (3.3) is the error-rate of the best randomized tester on the worst
input structure, when best is dened as the best worst-case. If the best randomized
tester with complexity c has an error-rate greater than 1/3 on an input, we can conclude
that the property in question is not testable with complexity c.

3.2.2 An Untestable Property
We will now prove that there exists an untestable property. The specic example that← ←we use is L := {uuv v}, where the underlying alphabet is {0, 1}. This is clearly a contextfree language and so Theorem 4 will also imply that there exist untestable context-freelanguages. The proof here is due to Alon et al. [4].
←In Theorem 1, we showed that LP = {uu} is testable. We might hope to use this← ←tester twice in an attempt to test L = {uuv v}, possibly iterating and taking the majority
decision in order to increase the success probability above 2/3. However, this assumes←←
that we know the divider between uu and v v in advance, which is not true. Our attempt
to use the tester from Theorem 1 is therefore unsuccessful, as we would be forced to search
for the divider by using the previous tester a linear number of times and make too many
queries. In the following theorem, we will show that it is not possible to test L using

18

3.2.

19

UNTESTABLE PROPERTIES√
any algorithm that makes o( (n)) queries. This is our rst example of a property thatis untestable.
←
Theorem 4 (Alon et al. [4]). The language L = {u←uv v}, where u and v are strings over√{0, 1} is not testable with complexity o( n).

The proof is an application of Principle 1, and so we begin by dening a distribution D of strings. Our goal is to show that D is such that all deterministic testers that√make c = o( n) queries have error rates greater than 1/3 for L. Principle 1 will then√
imply that L is not testable with o( n) queries, as desired. In the proof we will assume
that n is suciently large, although it is of course always nite. This will conveniently
allow us to assume that n is divisible by 6 (if it is not, use the rst multiple of 6 that islarger than n), avoiding the use of oors.
Distribution D draws from a distribution D+ of strings in L or from a distribution
D− of strings that are ε-far from L with probability 1/2 in each case. Distribution D−
selects a w ∈ {0, 1}n uniformly at random from the set of w such that dist(w, L) ≥ ε.
Distribution D+ rst selects a positive integer k ∈ {1, . . . , n/3}, and then selects stringsu ∈ {0, 1}k and v ∈ {0, 1}(n−2k)/2 , uniformly at random in each case. The result is a
← ←string w = uuv v ∈ L ∩ {0, 1}n . We can think of D+ as selecting a pair (k, w) and somew can be chosen with multiple values of k .
√We now consider an arbitrary deterministic tester A with complexity c = o( n).
As mentioned above, we can consider A to be a balanced binary tree and it therefore
has 2c leaves. We let T0 be the set of leaves labeled reject and T1 be the set ofleaves labeled accept. Additionally, we associate to each leaf t a sequence of c pairs
Qt := ((pt1 , r1t ), . . . , (ptc , rct )) corresponding to the bit positions queried (pti ∈ [0, n − 1])and the results (rit ∈ {0, 1}) on the path from the root of A to t. Furthermore, we deneq(Q, w) for w ∈ {0, 1}n to be true if w agrees with Q, or more formally, if bit pi in w
is ri for all 1 ≤ i ≤ c, and false otherwise.
We also dene E + (Q) (resp. E − (Q)) to be the set of strings with length n that agreewith Q and are positive (ε-far) instances for L. More formally,
Proof.

E + (Q) := {w | w ∈ L ∩ {0, 1}n and q(Q, w) is true} andE − (Q) := {w | w ∈ {0, 1}n , dist(w, L) ≥ ε and q(Q, w) is true} .
If we consider some xed accepting leaf t, then E − (Qt ) is the set of strings that A
makes an error on when ending in t and similarly for a rejecting leaf t and E + (Qt ). We
dene the probability of a set to be the sum of the probabilities of the members of theset, and therefore the total error of A is∑t∈T0

Pr(E + (Qt )) +
D

∑
t∈T1

Pr(E − (Qt )).
D√
We will show the following two lemmata for any sequence Q of o( n) elements.
19

3.2.

20

UNTESTABLE PROPERTIES

Lemma 2.

PrD (E + (Q)) = (1/2 − o(1))2−|Q| .

Lemma 3.

PrD (E − (Q)) = (1/2 − o(1))2−|Q| .

Every leaf of A must be labeled with exactly one decision, and so |T0 | + |T1 | = 2|Q| .
Using the two lemmata, the total error of A is then|T0 |(1/2 − o(1))2−|Q| + |T1 |(1/2 − o(1))2−|Q| =|T0 | + |T1 |(1/2 − o(1)) = (1/2 − o(1)).
2|Q|

The o(1) term approaches zero as n grows and so the error is greater than 1/3 for suciently large n. Therefore, by Principle 1, language L cannot be tested with complexity√o( n) and is therefore untestable.
We must now show the two lemmata used by the theorem. We will use the (loose)
upper bound |L ∩ {0, 1}n | ≤ 2n/2 n/2, which follows from the observation that we rstchoose the string uv and then choose the length of u to determine a w ∈ L. In addition,
if the length of u is xed at k , there are exactly 2n/2 corresponding w, which will be
useful given the denition of distribution P .
√Lemma 2. If |Q| = o( n), then PrD (E + (Q)) = (1/2 − o(1))2−|Q| .
Proof.

First, for any w ∈ {0, 1}n ∩ L, by the denition of D,∑n/3← ←k=1 |{u | ∃v : w = uuv v, |u| = k}|.
Pr(w) = 1/2 Pr (w) =DD+
2n/2 2n3

Next, it follows from the denition of E + (Q) that PrD (E + (Q)) = 21 PrD+ (E + (Q)) =(12n/2 2n/3

)∑
n/3

← ←

|{w | ∃u, v : w = uuv v, |u| = k and q(Q, w)}| .

k=1

If the sequence Q contains a pair of queries that are symmetric about k or n/2 + k ,←←then the pair queries the same bit in u and u or in v and v . If the results of these queries( )must be dierent, then it is impossible for such a w to exist. However, Q contains |Q|2( )pairs, and so there is no such pair of queries for at least n/3 − 2 |Q|
choices
of
k
.
For
2
each of these k ,← ←|{w | ∃u, v : w = uuv v, |u| = k and q(Q, w)}| = 2n/2−|Q| .
Therefore, as an upper bound,
)(
( ))
(
)(
|Q|
1
n/2−|Q|+2
n/3 − 2=
Pr(E (Q)) ≤n/2
D2
2 2n/3
(
( ))
2 |Q|
2
2−|Q| ,
1/2 −n/3√
which is (1/2 − o(1))2−|Q| for |Q| = o( n), as desired.
20

3.3.

21

CLOSURE PROPERTIES√

Lemma 3. If |Q| = o( n), then PrD (E − (Q)) = (1/2 − o(1))2−|Q| .
We noted above that the number of strings in L with length n is at most 2n/2 n/2
and so the number of strings of length n that are not ε-far from L satises
Proof.

(|{w | dist(w, L) ≤ ε, |w| = n}| ≤ 2n/2εn ( )
)∑
n
n/2
.
i
i=0

This is upper-bounded by 2n/2+2εn log 1/ε . Recall that E − (Q) is the set of w ∈ {0, 1}nsuch that dist(w, L) ≥ ε and w agrees with Q. Then, the size of E − (Q) must satisfy¯ −¯¯E (Q)¯ ≥ 2n−|Q| − 2n/2+2ε log 1/εn .
Then, by the denition of distribution D,

Pr(E − (Q)) = 1/2P rD− (E − (Q)) ≥D|E − (Q)|.
2nFor ε < 1/16, this is(1/2 − 2−Θ(n)+|Q| )2−|Q| = (1/2 − o(1))2−|Q| ,√where the last equality holds for |Q| = o(n). Our assumption is stricter, |Q| = o( n).
Theorem 4 allows a number of interesting corollaries. In particular, now that wehave seen that both testable and untestable properties exist, in the next section we will
examine closure properties of the set of testable properties.

3.3 Closure Properties
The language in Theorem 4 is the set of strings that are the concatenation of two evenlength palindromes. That is, it is the product LP LP , where LP is the language of binary
palindromes with even length proven testable in Theorem 1. We therefore immediately
get the following corollary.

Corollary 2. The testable properties are not closed under product.
In addition, the denition of testability is asymmetric in the sense that it requires us
to accept all positive instances with high probability while requiring us to reject, again
with high probability, only those negative instances that are also far from having theproperty.

Corollary 3. The testable properties are not closed under complement.
We use the complement of the language L from Theorem 4, L := {w | w 6∈ L}.
We begin by showing that for suciently large n, there is no w ∈ {0, 1}n such that
dist(w, L) ≥ ε.

Proof.

21

3.3.

CLOSURE PROPERTIES

22

Lemma 4. Given ε > 0, there is no w ∈ {0, 1}n such that dist(w, L) ≥ ε for n > 1/ε.
Let w ∈ {0, 1}n be arbitrary. There are two cases. If w ∈ L, then dist(w, L) =0 < ε. Therefore, assume that w ∈ L and n > 0. It is trivial to see that all strings in
L have an even number of 1s and an even number of 0s. We change the rst characterof w to its opposite, and call the resulting string w0 . The number of 1s in w was even,and therefore the number of 1s in w0 is odd (we have either removed one or added one).
Therefore, w0 cannot be in L and so it is by denition in L. We have only modied one
bit, and so dist(w, L) = 1/n < ε, where the inequality holds for n > 1/ε.
Lemma 4
Proof.

A tester for L can therefore simply verify that the input string is suciently long, i.e.,that n > 1/ε, and then accept. Membership for inputs that are not suciently long canbe computed exactly after querying all n ≤ 1/ε bits. This tester clearly accepts w ∈ Lwith no error. When ε > 0 is xed, if dist(w, L) ≥ ε, then n ≤ 1/ε, by Lemma 4. The
tester therefore queries every bit and rejects without error. The tester makes at most1/ε queries, which does not depend on n, and therefore L is testable.
However, by the denition of complement, L = L, which is not testable by Theorem 4
and so the testable properties are not closed under complement.
The above results are both negative. However, if we consider closure under union, we
obtain the following.

Theorem 5. The testable properties are closed under nite unions.
Proof. Recall that for all α, β ∈ (0, 1/2), if we have a tester which is correct with probability at least 1/2 + α, we can construct a tester which is correct with probability at least
1/2 + β by running the rst tester a constant number of times and taking the majority
output (see, e.g., Section 11.2 in Papadimitriou [35]). The number of iterations for xedreals α and β does not depend on n and so the number of queries in the new tester is aconstant multiple of the original number of queries.
Let P1 and P2 be two testable properties. Then, for every ε > 0, there exist testers T1ε(T2ε ) accepting inputs S that have property P1 (resp. P2 ) and rejecting inputs S wheredist(S, P1 ) ≥ ε (resp. dist(S, P2 ) ≥ ε). The discussion above allows us to assume that√the testers are correct in each case with probability at least 2/3. It is then simple toconstruct the following tester T ε for P1 ∪ P2 , for input I .

1. Run T1ε on I . If T1ε accepts, halt and accept.
2. Next, run T2ε on I and output its decision.
Clearly, T ε accepts inputs I that have property P1 or P2 with probability greaterthan 2/3. An input I that is ε-far from the property P1 ∪ P2 is ε-far from both P1 andfrom P2 . This is because, if I is ε-far from P1 ∪ P2 , then there is no I 0 ∈ P1 ∪ P2 suchthat dist(I, I 0 ) ≤ ε. By the denition of union this implies that there is no I 0 ∈ P1 suchthat dist(I, I 0 ) ≤ ε, and likewise for P2 .
22

3.4.

INDISTINGUISHABILITY

23

We therefore reject inputs which are ε-far from P1 ∪ P2 with probability at least√ 2
2/3 = 2/3 and so T ε is an ε-tester for P1 ∪ P2 , as desired.

3.4 Indistinguishability
When proving the testable properties are not closed under complement (Corollary 3),
we showed that all suciently long strings were close to the language L we were considering. That is, for all ε there is an upper bound on the length of strings w such that
dist(w, L) ≥ ε (Lemma 4).
This was our rst example of a concept called indistinguishability, which was dened
for graph properties by Alon et al. [2]. Roughly speaking, if we have two languages(properties) L1 and L2 such that all elements of L1 are close to L2 and all elementsof L2 are close to L1 , then we say the two languages (properties) are indistinguishable.
Because property testers only examine a very small portion of their inputs, the probability
that these testers will nd evidence that a w ∈ L1 is not actually in L2 is small. This
will allow us to show the most important result regarding indistinguishability, that itpreserves testability (Theorem 6).
Unfortunately, formally dening close enough is not trivial in our generalized setting.
Alon et al. [2] dened it for loop-free graphs, but we do not have the luxury of such
restrictions. Two structures are close enough if there is no dierence that can distinguishthem with high probability, and so simply using our denition of distance may not suce.
To see this, we consider a vocabulary with two relations, H of high arity and L of low
arity. The low arity relation contributes an asymptotically insignicant amount to the
distance of Denition 3 because the number of possible high arity tuples dominates anydierence in L assignments. Consider two large structures A and B with this vocabulary,
where A and B have identical H assignments and opposite L assignments. For ε > 0,
if these structures are suciently large, then dist(A, B) < ε. However, although thesestructures are very close, a tester could distinguish between them by examining only asmall number (one) of the L assignments.
We can use loops in graphs in a similar way, a graph possibly containing loops isequivalent to an loop-free graph with a monadic color relation. We therefore begin bydening a subtype of a relation.

Denition 10. Let R be a relation with arity a. Then, a subtype of R is a set of at
most a elements, each of which is a set containing integers from {1, . . . , a}. Each of these
integers must appear in exactly one of the elements of the subtype.

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 pair occurs
only in position 1 and the element in position 2 occurs only in position 2. That is, thissubtype is the set of edges that are not loops. The subtype {{1, 2}} then corresponds tothe set of edges that are loops. This can be more formally dened as follows.
23

3.4.

24

INDISTINGUISHABILITY

Denition 11. Let R be a relation with arity a and S be a subtype of R,
}
{
|S|
|S|
S = {t11 , . . . , t1b1 }, . . . , {t1 , . . . , tb|S| } .

i
A tuple (x1 , . . . , xa ) belongs to S if for all t1 , it is the case that xti = xti for all j and,1j

if xu = xv for some u, v then u and v are both contained in the same element of S .

It is harmless but useless for the same i to appear multiple times in the same elementof a subtype. We now dene the S−distance between structures, where S is a subtypeof relation Ri .

Denition 12. Let A, B ∈ STRUC n (τ ) be structures with universe U and vocabulary τ ,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|

The S -distance is the fraction of tuples belonging to S that are given dierent assignments by Ri in A and B . We dene the Ri -distance to be the maximum S -distance forsubtypes S of Ri . If the maximum Ri -distance between two structures is very small, allof the subtypes of all the relations are very similar, and there is no special query thathas a high probability of nding a dierence.
Let SU B(R) be the set of subtypes of relation R. Then, the maximum Ri -distance isthe following.

Denition 13. Let A, B ∈ STRUC n (τ ) be structures with universe U and vocabulary τ .
Then, the maximum Ri -distance between A and B is

max Ri -dist := max

1≤i≤s

max

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

When dening indistinguishability, we use the maximum Ri -distance. Note that
dist(A, B) ≤ maxi Ri -dist(A, B), which we show as part of Theorem 9 in Section 3.7.
The Ri -distance is equal to the usual distance for vocabularies with exactly one predicate symbol if it has one subtype, such as loop-free graphs or binary strings.
We generalize our denition of Ri -distance in the following way, where P is a property.

Denition 14. Let A ∈ STRUC n (τ ) be a structure and P be a property of type τ . Then,the Ri -distance between A and P is

Ri -dist(A, P ) :=min

{B∈P |#(B)=n}

Ri -dist(A, B).

If the minimum is taken over an empty set, we dene the distance to be innite.

Properties that are closed under isomorphisms are most natural in property testing,
and we now dene this idea.

Denition 15. Let A, B ∈ STRUC n (τ ) be structures with vocabulary τ . We call A
isomorphic to B if there is a mapping φ : {0, . . . , n − 1} 7→ {0, . . . , n − 1} such that
24

3.4.

INDISTINGUISHABILITY

25

1. The mapping φ is bijective;A
2. For all Ri ∈ τ and all (x1 , . . . , xai ), it is true that Ri (x1 , . . . , xai ) if and only if
RiB (φ(x1 ), . . . , φ(xai )).

The mapping φ is called an isomorphism. We dene properties to be closed underisomorphisms in the following way.

Denition 16. Let P be a property of type τ . We say that P is closed under isomorphisms if for all n ∈ N and all A, B ∈ STRUC n (τ ), if A and B are isomorphic thenA ∈ P if and only if B ∈ P .
We note that given the lack of ordering, all properties that can be expressed by formulasin our logic are closed under isomorphisms, although we do not use this assertion here.
We are now nally ready to dene indistinguishability. In the case of loop-free graphs it
is equivalent to the denition given by Alon et al. [2].

Denition 17. Two properties P and Q of structures with vocabulary τ are said to beindistinguishable if they are closed under isomorphisms and for every ε > 0 there exists
an Nε such that for any structure A with vocabulary τ and universe of size n ≥ Nε , if A
has P then maxi Ri -dist(A, Q) ≤ ε and if A has Q then maxi Ri -dist(A, P ) ≤ ε.
It is worthwhile to note that indistinguishability is an equivalence relation. It is clearly
symmetric and reexive, and transitivity is also simple to show. Assume that P is
indistinguishable from P2 , which is in turn indistinguishable from P3 . For suciently
large A, if A has P1 then there is a B that has P2 such that maxi Ri -dist(A, B) ≤ ε/2 andlikewise for B and a C that has P3 . Then, maxi Ri -dist(A, P3 ) ≤ maxi Ri -dist(A, C) ≤ ε,as desired.
The importance of indistinguishability is expressed by the following theorem, which
was shown by Alon et al. [2] for the case of graphs. Their proof works nearly verbatim
in our setting.

Theorem 6. If P and Q are indistinguishable, then P is testable if and only if Q is
testable.

We assume without loss of generality that P is testable and provide an ε-tester
for Q. By assumption, P is testable and so there exists an ε/2-tester T ε/2 for P thatmakes at most c(ε/2) queries. The tester accepts structures A that have P and rejects
those that are ε/2-far with probability at least 2/3 in both cases.
Let N be such that for structures A of size n ≥ N , if A has Q then maxi Ri -dist(A, P ) ≤)(2. The 2/(81c) appears because we would like to use a trick similar to thatmin ε/2, 81c
in Theorem 1, and this will cancel nicely because 81 = 3 · 27.
We will test input A for Q in the following way.
Proof.

1. If #(A) ≤ N , query all of A and output an exact decision.
25

3.5.

TESTABLE PROPERTIES THAT ARE HARD TO DECIDE26

2. Otherwise, run T ε/2 three times on A, using random permutations of the labels of
A each time. Output the majority decision.
The restriction that the properties are closed under isomorphisms allows us to use therandom permutations in Step 2. This tester makes at most 3c := 3c(ε/2) queries and has
a success probability of at least 2/3. Assume that n = #(A) is suciently large. If A is
ε-far from Q, it is also ε/2-far from P . Therefore, T ε/2 will reject A with probability atleast 2/3 and our tester correctly rejects with probability at least 20/27 > 2/3.
Now, assume that A has Q. Then, there exists an A0 that has P such that A and A02
dier in no more than a 81c
fraction of the possible assignments, for every subtype andevery relation. The probability that any particular query will see one of these assignments
2
is at most 81c
and so the probability that any of the 3c queries will see one of these bits()
2 3c
is at most 1 − 1 − 81c≤ e−2/27 ≤ 2/27. The probability of success is then at least
20/27 − 2/27 = 2/3 and so Q is testable, as desired.
Indistinguishability is an equivalence relation on properties that preserves testability.
It therefore partitions the set of properties into equivalence classes such that each classcontains only testable properties or only untestable properties. However, in the generalcase only non-uniform testability is preserved, as we will see in Section 3.6. Alon et al. [2]used indistinguishability as a tool for proving classes of properties to be testable, as we
will, but it is likely to be of more general interest.

3.5 Testable Properties that are Hard to Decide
We have already seen that there exist context-free languages that are testable (Theorem 1) and also some that are not testable (Theorem 4). However, the relationshipof the testable properties with the traditional complexity hierarchy is worthy of moreinvestigation. Goldreich et al. [20] have shown that there exist testable NP-complete
properties. Assuming P 6= NP, this means that there exists properties for which it isvery easy to decide if the input nearly satises the property but quite hard to decide theproblem exactly. Here we will show that this gap is much larger: There exist properties
for which it is very easy to decide if the input nearly satises the property but extremelydicult to decide exactly.
In this section we show the existence of testable properties that are arbitrarily hard to
decide exactly. The testable properties therefore extend arbitrarily high in the traditional
hierarchy, but, by Theorem 4, do not contain even the context-free languages.
We dene arbitrarily hard properties as meaning, for every computable f (n), containing properties that are not decidable in DTIME(f (n))1 .
It suces to consider loop-free graph properties, where the maximum Ri -distance isequal to the usual distance. The same result can also be shown for other vocabularies.
1

The choice of DTIME here is arbitrary and other complexity measures such as DSPACE result in

equivalent denitions.

26

3.6.

UNIFORMITY CONDITIONS

27

Theorem 7. There are arbitrarily-hard testable properties.
Let P be an arbitrarily-hard property. We dene a property Q such that P
reduces to Q. Let p(x) be the characteristic function for P on some reasonable encodingof the input. We dene Q to be true for graph G of size n i the number of edges in G
is equal to p(n).
We can obviously reduce P to Q by, on input x, computing the encoding x and outputting a graph on x vertices with exactly one edge. We can therefore construct arbitrarily hard properties Q.
It is worth noting that this reduction increases the input length by an exponential
factor. Because we are only interested in arbitrarily hard properties and by the timehierarchy theorem (see Hartmanis and Stearns [25]), we can simply choose P such that
it is not computable in DTIME(2f (n) ) to construct a property Q that is not computablein DTIME(f (n)).
Property Q is indistinguishable from the property of being the empty graph, which we
showed to be testable in Theorem 2. If a graph G has property Q, it is either empty or
it has one edge, and so the maximum Ri -distance is at most 1/n2 . The converse is thesame, an empty graph either has Q or the distance is at most 1/n2 . Obviously, 1/n2 < ε√for n > 1/ε and so the properties are indistinguishable.
We showed in Theorem 2 that being the empty graph is testable, and therefore, byTheorem 6, so is Q.
Proof.

3.6 Uniformity Conditions
We encoded the characteristic function for an arbitrary property while proving Theorem 7. There was no particular requirement for the property to be decidable. The
existence of undecidable properties that are testable warrants additional consideration.
We noted that our denition of testability (Denition 6) is non-uniform in the sensethat it does not require the various ε-testers to be computable given ε. It is reasonable
to expect a situation similar to that of circuit complexity classes such as AC0 , where
the non-uniform versions contain undecidable properties and the uniform versions do not(see, for example, Straubing [45]). We will see that this is the case, thereby showing thatthe non-uniformly testable properties strictly contain the uniformly testable properties.
Alon and Shapira [8] have shown the same separation by using a decidable graph property.
That probabilistic machines do not compute properties that are deterministically uncomputable was rst shown by de Leeuw et al. [30]. We have dened ε-testers to berandomized algorithms, and so we assume that the probability of a given choice being
made by an ε-tester is a computable real number. Machines that make choices with
noncomputable probabilities have additional power, see, e.g., de Leeuw [30].
We again consider loop-free graph properties and so the maximum Ri -distance is theusual distance.

27

3.6.

UNIFORMITY CONDITIONS

28

Theorem 8. There exist undecidable properties that are (non-uniformly) testable.
We dene a graph property P that is not decidable but is testable. As shown in
Hopcroft and Ullman [26], there is an enumeration of all and only Turing machines. Let
Mi refer to the i-th machine in this enumeration. A graph G with size n has property
P i either G is empty and Mi does not halt on the empty string, or G has exactly oneedge and Mi does halt on the empty string.
First, P is clearly undecidable. Given i, the problem of deciding whether machine Mi
halts on the empty string is a canonical RE-complete property, and it is simple to reduce
this to P . On input i, output a graph with i vertices and exactly one edge.
P is indistinguishable from the empty graph in exactly the same way as in the proof
to Theorem 7 and so it is testable.
√
The non-uniformness of these testers can be seen by observing that for n < 1/ε weare required to decide, correctly with high probability, whether machine Mi halts on theempty string. Once ε is xed, there are only a nite number of machines for which wemust decide this question, and so their behavior can be given in a nite list. However,in the case of uniform testability, we must be able to construct these nite lists for every
value of ε, which would contradict the undecidability of P .
We show this more formally in the following. All uniform testers are probabilistic
machines and, by choosing ε > 0 as a function of n, we can remove the approximation
in probabilistic approximation algorithm. Of course we then make a number of queries
that depends on the input size.
Proof.

Proposition 1. All uniformly testable properties can be decided by a probabilistic Turingmachine with success probability at least 2/3.

Assume property P of structures with vocabulary τ is testable. On input A with∑
universe size n, choose ε such that ε < 1/ i nai , for example, ε = 1+P1 nai . Run theiε-test on A and output the result. The tester must dierentiate between inputs having
P and inputs being ε-far from having P . For A, a structure with universe size n, it must
therefore distinguish between those that have the property and those that do not, withprobability 2/3, as desired.
Proof.

Corollary 4. All uniformly testable properties are decidable.
Convert the probabilistic machine of Proposition 1 using the following genericconstruction.
All probabilistic machines can be modied such that their randomness is taken froma special binary random tape that is randomly xed when the machine is started, inwhich each digit is 0 or 1 with equal probability.
All halting probabilistic machines must eventually halt, regardless of the random
choices made. We can then simulate the machine over all initial segments of increasing lengths, keeping track of accepting, rejecting and still running states. Once any
Proof.

28

3.7.

ALTERNATE DEFINITIONS OF DISTANCE

29

given segment has halted, all random strings beginning with that initial segment mustalso halt. Therefore, the percentage of halting paths is increasing, and we shall eventuallyreach a length such that at least 7/10 of the paths have halted. Our error probability
is at most 1/3, strictly less than half of 7/10 and so we can output the decision of the
majority of the halting paths.
Theorem 8 and Corollary 4 immediately yield the following separation. A dierent
proof using a decidable property has been given by Alon and Shapira [8].

Corollary 5. There exist properties that are non-uniformly testable but not uniformly
testable.

3.7 Alternate Denitions of DistanceDenition 3 denes the distance between structures to be the fraction of assignments on
which they disagree. As we saw in Section 3.4, this means that any possible dierence inthe assignments of low-arity relations is dominated by the number of high-arity tuples. In
some sense this is a natural denition, as the number of low-arity tuples is asymptoticallyinsignicant and so two structures are close if most of their assignments agree.
However, there are situations where this denition may not be ideal. Vertex-coloredgraphs are graphs in which each vertex is assigned one of some (usually constant) number of colors. We say that the coloring is admissible if for all (x, y) ∈ E , vertices
x and y have dierent colors. If we consider 3-colored graphs with the vocabulary
τC := {E 2 , R1 , G1 , B 1 } we might be interested in testing whether the given coloringis admissible or not. If we use our usual denition of coloring, this is equivalent totesting whether the graph is 3-colorable and ignores (for suciently large graphs) the
existing coloring. If we wish to test whether the given coloring is nearly admissible, weneed a slightly dierent model.
In this section we present a number of alternate denitions 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 denition of distance changes
the task of testing. We will also show the relationships between the sets of testableproperties that arise from each of our denitions. As in Denition 3, the symbol ⊕denotes exclusive-or.

Denition 18. Let A,B ∈ STRUC (τ ) be structures such that #(A) = #(B) = n. The
r-distance between structures A and B is|{x | x ∈ U ai and RiA (x) ⊕ RiB (x)}|
.
1≤i≤s
nai

rdist(A, B) := max

That is, the r-distance is the maximum over the relations Ri of the fraction of Ri assignments diering between A and B . While Denition 3 gave equal weight to eachtuple, regardless of its arity, this denition gives equal weight to each relation. Tuples
29

3.7.

ALTERNATE DEFINITIONS OF DISTANCE

30

with lower arity can then be considered to have greater weight than those with higher
arity. We will also consider the maxi Ri -distance (which we will shorten to mrdist(A, B)),
which was dened using subtypes in Section 3.4 (cf. Denition 13).
We begin by showing the following simple relationship between these distances.

Theorem 9. Let τ be a vocabulary and A, B ∈ STRUC (τ ) be structures such that#(A) = #(B). Then,dist(A, B) ≤ rdist(A, B) ≤ mrdist(A, B).
Proof. We begin by showing dist(A, B) ≤ rdist(A, B). Essentially, if dist(A, B) = ε thenan ε-fraction of the total assignments diers. If we then partition the total assignments,
there must exist a partition such that at least an ε-fraction of the assignments diers inthat partition.
Let dist(A, B) = ε and let αi be the fraction of Ri -assignments that diers between
the structures, i.e.,

αi :=|{x | x ∈ U ai and RiA (x) ⊕ RiB (x)}|.
naiThen, rdist(A, B) = maxi αi and we can write dist(A, B) in terms of the αi :∑αi naidist(A, B) = ∑i a = ε.
iin∑∑This implies that i αi nai = ε i nai . We do not know the values ai , but if equality
holds there must be at least one αi satisfying αi ≥ ε. This implies that dist(A, B) ≤rdist(A, B), as desired.
Next, we show that rdist(A, B) ≤ mrdist(A, B). The proof is nearly identical to theabove. If rdist(A, B) = ε then there is an Ri such that an ε-fraction of the Ri -assignmentsdiers between the structures. If we partition the Ri -assignments into the subtypes of Ri(which are disjoint), then there must be some partition such that at least an ε-fractionof the assignments in that partition dier. As above we let rdist(A, B) = ε. Let Ri bea relation such that the Ri -distance between A and B is ε and let αj be the fraction of
assignments in subtype Sj of Ri that dier between the structures. Using the notationof Section 3.4, i := arg maxk Rk -dist(A, B) and αj = Sj -dist(A, B) for subtypes Sj of Ri .
Then, mrdist(A, B) = maxj αj and∑j αj |Sj |= ε.
rdist(A, B) = ∑j |Sj |
By exactly the same argument as above, there must exist an αj ≥ ε and so rdist(A, B) ≤mrdist(A, B).
There exist vocabularies such as τS = {S 1 } where equality is attained in each of theabove inequalities and also vocabularies where equality is not attained.
30

3.7.

ALTERNATE DEFINITIONS OF DISTANCE

31

Theorem 9 immediately admits the following nice corollary, where we let T be the setof testable properties with our usual denitions, Tr be the set of testable properties using
the rdist denition for distance and Tmr be the set of testable properties using the mrdist
denition for distance.

Corollary 6. Tmr ⊆ Tr ⊆ T .
Assume we have a Tmr ε-tester for property P . Then, it distinguishes with probability at least 2/3 between structures with P and structures A such that mrdist ≥ ε.
We will show that this is also a Tr ε-tester for P . Let A denote the input structure. If A
has property P then our tester accepts with probability at least 2/3, as desired. We saw
above that rdist(A, B) ≤ mrdist(A, B) and so if rdist(A, B) ≥ ε then mrdist(A, B) ≥ ε
and the tester rejects with probability at least 2/3, as desired.
The proof of Tr ⊆ T is analogous to the above.
Proof.

In fact, we can show both of these inclusions are strict and so it is strictly easier totest using Denition 3 than the others. Of course, it is possible for equality to hold if
we restrict ourselves to a xed vocabulary. We have noted above that the denitions
are all equivalent in the case of binary strings. In the case of graphs or other structureswith exactly one predicate symbol which is not monadic, rdist(G, G0 ) = dist(G, G0 ) andso testing these properties with the dist denition is equivalent to testing with the rdist
denition for distance. The proof of Theorem 10 will show that testing such properties
with the mrdist denition for distance is not equivalent.

Theorem 10. Tmr ⊂ Tr ⊂ T .
The inclusions are shown in Corollary 6 and so it suces to show the separations.
We begin by showing that T \Tr is not empty. To do this we consider the vocabulary
τC := {E 2 , S 1 } which we can interpret as the vocabulary of (not necessarily admissible)
one-colored graphs.
We will show that P1 ∈ T \Tr , where P1 is the set of structures A with vocabulary τC← ←such that the S assignments encode the language L = {uuv v} from Theorem 4. That
is, A has P1 if there is some 0 ≤ k ≤ n/2 such that for all 0 ≤ i < k , S(i) is true iS(2k − 1 − i) is true and for all 0 ≤ j < (n − 2k)/2, S(2k + j) is true i S(n − 1 − j)is true. The property is decided only by the low-arity relation S ; the E relation exists
only to provide padding so that the property is testable using the dist denition for
distance.
We begin by showing that P1 is testable using Denition 3. An input structure A
with a universe of odd size cannot have P1 . With our denitions, a tester can begin bychecking the parity of n and then reject if it is odd. We can therefore assume in thefollowing that the size of the universe is even. It is also possible to dene P slightlydierently to avoid this problem, for example requiring the S assignments to be of the← ←← ←form uuv v or 1uuv v . However, it is simpler for us to be consistent with Theorem 4.
Proof.

Lemma 5. Property P1 is testable under the dist denition for distance.
31

3.7.

ALTERNATE DEFINITIONS OF DISTANCE

32

The proof is similar to that of Corollary 3. We again begin by showing that forsuciently large n, there is no structure A with universe size n such that dist(A, P1 ) ≥ ε.
← ←For any (even) n, there exist possible w ∈ {0, 1}n that are of the form uuv v , suchas 1n . Given A we create A0 by changing all S(i) assignments to be true. This involves
at most n modications and so dist(A, P1 ) ≤ dist(A, A0 ) = O(n)/Θ(n2 ) < ε, where thenal inequality holds for suciently large n. Let N (ε) be the smallest value of n forwhich the inequality holds. Then, the following is an ε-tester for P1 , where the input hasuniverse size n.
Proof.

1. If n < N (ε), query all assignments and output whether the input has P1 .
2. Otherwise, accept.
If the input A has P1 , we will accept with zero error. If dist(A, P1 ) ≥ ε, then n < N (ε)
by the above. In this case we query all assignments and will reject with zero error.
Lemma 5It remains to show that P1 is not testable when using the rdist denition for distance.
We do this by showing that if it were testable under the rdist denition, we would be← ←able to construct testers for {uuv v}, contradicting Theorem 4.

Lemma 6. Property P1 is not testable under the rdist denition for distance.
Proof. Assume that P1 is testable under the rdist denition for distance. Then, there
exist ε-testers T ε using this denition for all ε > 0. We will show that the following is anε-tester using Denition 3 for the language L of Theorem 4. We denote the input withw and note that w is a binary string with vocabulary τS = {S 1 }.

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 ε .
That is, given a string w, we simulate T ε on the structure A ∈ STRUC (τC ) thathas the same universe size as w, agrees with w on the S assignments and where all E
assignments are false.
Assume that w ∈ L and let n be the size of the universe. Then, any A ∈ STRUC (τC )with universe size n that satises ∀i : S w (i) ↔ S A (i) has property P1 . That is, if w and
A agree on the S assignments, w ∈ L implies A ∈ P1 . In this case, T ε will accept A
with probability at least 2/3. Therefore, our tester will also accept w with probability
at least 2/3, as desired.

32

3.7.

ALTERNATE DEFINITIONS OF DISTANCE

33

Now, assume that dist(w, L) ≥ ε. In this case, rdist(A, P1 ) = dist(w, L) ≥ ε and so T εwill reject A with probability at least 2/3. Our tester will therefore reject such w withprobability at least 2/3 as desired.
We have constructed ε-testers for the language L shown to be untestable in Theorem 4,
and therefore P1 must be untestable under the rdist denition of distance.
Lemma 6
Lemmata 5 and 6, together with Corollary 6 show Tr ⊂ T . We now show the separation
Tmr ⊂ Tr . The proof is similar: We construct a property where there is sucientpadding to make Tr testing simple but Tmr testing would contradict Theorem 4.
We use the following property P2 of graphs (τG = {E 2 }). A graph G has P2 if the← ←loops E(i, i) encode the language {uuv v} from Theorem 4. That is, P2 is determined
only by the linear number of loops and the remaining E assignments can be arbitrary.
More formally, a graph G with universe size n has P2 if there exists some 0 ≤ k ≤ n/2
such that for all 0 ≤ i < k , E(i, i) is true i E(2k − 1 − i, 2k − 1 − i) is true and for all
0 ≤ j < (n − 2k)/2, E(2k + j, 2k + j) is true i E(n − 1 − j, n − 1 − j) is true.
As before, we rst show that P2 is testable using the rdist denition for distance. The
tester can again begin by checking the parity of the universe, and so we assume that n
is even.

Lemma 7. Property P2 is testable under the rdist denition for distance.
As before, we begin by showing that for suciently large n, there is no graph G
with universe size n such that rdist(G, P2 ) ≥ ε.
Recall that for all (even) n there exist possible w ∈ {0, 1}n that are of the form← ←uuv v , for example 1n . Given G we create G0 by changing all E(i, i) assignments to betrue. This involves at most n modications. There is only one relation symbol, and so
rdist(G, P2 ) = dist(G, P2 ) ≤ dist(G, G0 ). There are n2 possible E assignments, and so
this is O(n)/n2 < ε where the inequality holds for suciently large n. Letting N (ε) be
the smallest value of n for which the inequality holds, we can easily construct a tester asin Lemma 5 by replacing  P1  with  P2 .
Lemma 7
Proof.

It remains to show that P2 is not testable under the mrdist denition for distance.
The proof is nearly identical to that of Lemma 6; given a Tmr style tester for P2 , we
← ←construct testers using Denition 3 for the language {uuv v} that was proven untestablein Theorem 4.

Lemma 8. Property P2 is not testable under the mrdist denition for distance.
Assume that P2 is testable under the rdist denition for distance. Then, there
exist ε-testers T ε using this denition for all ε > 0. We will show that the following isan ε-tester using Denition 3 for the language L of Theorem 4. We denote the input by
w and note that it is a binary string with vocabulary τS = {S 1 }.
Proof.

1. Run T ε and intercept all queries.

33

3.7.

ALTERNATE DEFINITIONS OF DISTANCE

34

2. When a query is made for E(i, i), return the value of S(i) in w.
3. When a query is made for E(i, j) and i 6= j , return 0.
4. Output the decision of T ε .
Given a string w, we simulate T ε on the graph G with loops in the graph corresponding to bits of w and all other edges absent. Note that G has the same universe size as w
and that G has P2 i w ∈ L. Therefore, if w ∈ L, our tester will accept with probability
at least 2/3, as desired.
Now, assume that dist(w, L) ≥ ε. There are exactly two subtypes of a binary relation:
the loops and the non-loops. The S -distance (see Denition 12) for the subtype S
of non-loops is zero, and so mrdist(G, P2 ) = SL -dist(G, P2 ) where SL is the subtypeof loops ({{1, 2}}). This in turn is equal to dist(w, L) by the denition of G and so
mrdist(G, P2 ) ≥ ε. The tester T ε will then reject G with probability at least 2/3, and so
our tester will reject w with probability at least 2/3.
Lemma 8
Lemmata 7 and 8, together with Corollary 6 yield the desired Tmr ⊂ Tr . We have
Theorem 10
already shown Tr ⊂ T and so the proof is complete.

34

35

Chapter 4

The Classication Problem for
Testability
In this section we consider the classication problem of rst-order logic for testability.
That is, our goal is to reach a complete classication of the prex classes of rst-orderlogic into testable classes (those that contain only testable properties) and untestableclasses (those that contain an untestable property). This program is inspired by the
traditional classication problem, that of decidable and undecidable classes, and also by
results in property testing related to the testability of certain logical classes such as thoseby Alon et al. [2].
We begin by briey describing the traditional classication problem, and in particularfocus on the results that allow us to draw parallels to recent results in property testing.
Next, we introduce the previous results that begin a classication for testability. Finally,
we prove an additional class, traditionally known as Ackermann's class with equality, tobe a testable class and briey mention a few open problems.

4.1 History of the Classication Problem
Here we outline some of the history of the traditional classication problem, focusing
especially on results where we can draw an explicit comparison with testability results.
Börger et al. [11] provide the complete classication and its history, as well as proofs andan overview of related topics.
The classical decision problem was considered the central problem of logic in the 20th
century. In this problem, we are given a sentence of rst-order logic and wish to decide
whether or not it is satisable (or, roughly equivalently, valid). Although Church andTuring showed the problem to be undecidable in general, Löwenheim [32] had shownin 1915 that the monadic case is decidable. There was therefore an enormous eort tounderstand exactly which classes of formulas are decidable and which classes are not.
The traditional classication problem is now considered to be essentially resolved and acomplete classication has been obtained. By complete we mean that for any prex class
35

4.1.

HISTORY OF THE CLASSIFICATION PROBLEM

36

of rst-order logic, either the class is contained in a class that is classied as decidable
or it contains a class that is classied as undecidable. That such a complete and niteclassication exists seems to be quite fortunate.

4.1.1 Gurevich's Classiability Theorem
That a complete and nite classication of the prex vocabulary classes of rstorder logic exists is explained by Gurevich's Classiability Theorem (see Section 2.3
of Börger et al. [11]). Fortunately, this phenomenon is not restricted to decidability
and the theorem gives sucient criteria for such a classication to exist. A complete
statement and proof can be found in Börger et al. [11] while Gurevich [24] gives a niceintroduction to the theorem and its history.
We can summarize Gurevich's Classiability Theorem in the following way. Let D
refer to the set of prex vocabulary classes that have the property in question (in ourcase, D is the set of testable prex vocabulary classes) and U refer to its negation (theuntestable prex vocabulary classes). Then, if D is closed downward and under nite
unions, there exists a nite set M of the minimal closed classes of U such that U is the
upwards closure of M and all members of M are standard1 .
The testable classes are closed downwards and we have shown (Theorem 5) that they
are closed under nite unions. Therefore, there exists a nite set M of standard classes
such that every prex vocabulary class that contains an untestable property also contains
one of the classes in M . Written in a table, M is a nite way to give a complete
classication of the prex vocabulary classes for testability.
Our goal of eventually nding a complete characterization of the testable prex classes
is then obtainable: there exists a nite table providing such a classication. In thefollowing section we state some of the classical results for the classication for decidability
and compare them with what is known regarding the classication for testability. It is
worth noting that we do not necessarily state the optimal classical results, but instead
focus on those that closely parallel the known results for testability.

4.1.2 Classication Similarities
Monadic rst-order logic2 was the rst fragment of rst-order logic to be proven decidable. We begin with this result, which is due to Löwenheim [32]. This subsection is an
overview of the similarities and does not contain proofs. Later results in Subsection 4.3
depend on the testability results for monadic rst-order logic, which we review moreformally in Section 4.2.
Monadic logics are very well studied in the literature. Of particular relevance to us are
the results connecting these logics to formal languages. Perhaps the most well-known is
1
2Standard classes are those with nice representations in our notation, see Börger et al. [11].
Monadic rst-order logic is the set of formulas in which all predicate symbols are monadic.

36

4.1.

HISTORY OF THE CLASSIFICATION PROBLEM

37

Büchi's [12] result that monadic second -order logic characterizes the regular languages.
We are focused on (a very restricted) rst-order logic, but we can at least conclude that
all monadic rst-order formulas express regular properties, given that monadic rst-orderlogic is a subset of monadic second-order logic.
More immediately relevant is the result by McNaughton and Papert [33] that monadic
rst-order logic characterizes the star-free regular languages. Their denition of rstorder logic includes an ordering predicate ≤ as well as some additional arithmetic thatis not present in our logic, and so the properties expressible in our rst-order logic are astrict subset of the star-free regular languages.
In any case, the star-free regular languages are a subset of the regular languages.
Together with the result by Alon et al. [4], this immediately implies that all properties
expressible in monadic rst-order logic are testable. Using an extension of our notationfrom Section 2.4, we can say that [all, (ω)]= is testable. This is the class proven decidable
by Löwenheim [32], providing the rst similarity between the classication for decidability
and that for testability.
However, we can say more than this. As previously mentioned, Büchi [12] showedthat monadic second -order logic characterizes the regular languages. As Alon et al. [4]themselves note, the combination of their result and Büchi's implies that all monadic
second-order formulas express testable properties. This is not part of the classication
problem for rst-order logic, but it is worth making a comparison with Skolem's [43]extension to second-order logic of Löwenheim's result. That is, monadic second-orderlogic is another example of a class that is both testable and decidable.
If we return to rst-order logic, Skolem [44] showed a prex vocabulary class to be a
reduction class. As a result of developing Skolem Normal Form, he showed the class of
formulas where all universal quantiers precede all existential quantiers, [∀∗ ∃∗ , all] is areduction class. Although it was of course unknown at the time, this implies that theclass is undecidable. This class is not a minimal undecidable class and Skolem's result
was later improved.
Alon et al. [2] considered testing graph properties and showed there exists an untestableproperty (an encoding of graph isomorphism) that is expressible in [∀∗ ∃∗ , (0, 1)]= . This
is not identical to the undecidable class considered by Skolem [44], but it is close enoughto be interesting. Among the several improvements of Skolem's result is, for example,
Surányi's [46] result that [∀3 ∃, (0, ω)] is a reduction class. The encoding of graph isomorphism shown to be untestable by Alon et al. [2] can be expressed as a formula with twelve
universal quantiers and ve existential quantiers3 while Theorem 12 below implies that
one universal quantier is not enough to express any untestable graph property. It would
be worthwhile to attempt to nd the minimum number of quantiers needed to express
such a property, and also to look at other encodings of isomorphisms.
Alon et al. [2] also showed a positive result: that [∃∗ ∀∗ , (0, 1)]= is testable. The restriction to graphs here is more unfortunate. The class [∃∗ ∀∗ , all]= for pure predicate logic is3

That is, by a formula in [∀∃ , (0, 1)]= .

12 5

37

4.2.

TESTABILITY OF MONADIC FIRST-ORDER LOGIC

38

very well-known and generally called Ramsey's class. This is a maximal decidable classwhose decidability was rst shown by Ramsey [37]. A generalization of the testability
result to arbitrary vocabularies would be very desirable.

4.2 Testability of Monadic First-Order Logic
In Subsection 4.1.2 we mentioned that we can combine the result by McNaughton andPapert [33] that monadic rst-order logic4 characterizes the star-free regular languages
with that of Alon et al. [4] showing the regular languages are testable. This allows us toconclude that all properties expressible in monadic rst-order logic are testable. However,
we will use this result in our proof for the testability of Ackermann's class with equality
in Section 4.3, and so we consider this combination more formally.
Our goal is to prove that monadic rst-order logic, as we have dened it, expresses
only testable properties. Our denition of rst-order logic does not contain ordering or
symbols for successor and predecessor, unlike the denitions used by McNaughton andPapert [33].
The proof is structured in the following way. First, in Subsection 4.2.2 we show that all
properties expressible by monadic rst-order sentences can be expressed in a certain way
which we can easily translate to a regular expression. Regular expressions characterize
the regular languages and so all of our properties are regular. This part of the proof isbased on that given by McNaughton and Papert [33] although our version is simplied
due to the absence of the ordering and other symbols mentioned above.
Next, Alon et al. [4] have shown that all regular languages are testable. The proof
uses the characterization of regular languages as nite automata. We omit the detailed
proof here for space considerations. Basic results concerning the regular languages, suchas the equivalence of regular expressions and nite automata, can be found in Hopcroft
and Ullman [26].

4.2.1 Basics
Our proofs will use the vocabulary τM := {R11 , . . . , Rs1 }, and so there are s monadic
predicate symbols named Ri . As always, if the universe of such a structure has size n, welabel it with the non-negative integers {0, 1, . . . , n − 1} and map these to the character
positions of n-character strings from left to right. That is, universe member 0 corresponds
to the leftmost character position in the string and n − 1 to the rightmost.
Regular languages are dened over alphabets, traditionally denoted by Σ. The alphabet corresponding to τM will have 2s symbols, which we will name with binary strings oflength s in the obvious way, Σ := {00 · · · 00, . . . , 11 · · · 11}. These denote the possible assignments Ri (x) for some xed character position x. For example, the leftmost character
4

Their denition of monadic rst-order logic allows ordering and other symbols that are not present

in ours.

38

4.2.

TESTABILITY OF MONADIC FIRST-ORDER LOGIC

39

in a string is 00 · · · 00 i Ri (0) is false for all 0 ≤ i ≤ s. Likewise, the rightmost characteris 00 · · · 01 i Ri (n − 1) is false for all 0 ≤ i < s and Rs (n − 1) is true. Any reasonableencoding will work provided that the character at position i can be determined using a
constant number of queries. We will use c to denote characters in Σ.
The basic idea is to treat formulas ∃x : ψ with the regular expression Σ∗ RΣ∗ , where
R is a union over the characters for which ψ holds true. More complicated formulas arehandled largely by using the closure properties of regular languages.

4.2.2 Monadic First-Order Logic is Regular
The goal of this subsection is to show the following theorem. This is a weaker result
than that shown by McNaughton and Papert [33].

Theorem 11. All properties expressible in monadic rst-order logic are regular languages.

We are given a monadic rst-order formula ϕ of type τM = {R11 , . . . , Rs1 }. Without
loss of generality, we can assume that ϕ is in prenex normal form and by renaming thevariables, that no variable is bound by more than one quantier. We rename the variables
to be x1 , . . . , xa in order, so that ϕ is of the form
Proof.

ϕ = π1 x1 π2 x2 · · · πa xa : ψ
where each πj is either ∃ or ∀ and ψ is quantier free.
Regular expressions are inherently ordered in the sense that they are written from left
to right. However, we do not know if x1 < x2 in formulas such as ∃x1 ∃x2 : ψ . This will
be handled by breaking the formula into a disjunction of three formulas, each enforcing
an order. One formula will correspond to x1 < x2 , one to x1 > x2 and one to x1 = x2 .
We do this by using restricted quantiers.

Denition 19. Quantiers of the form ∃ττ21 x : ψ or ∀ττ21 x : ψ are restricted quantiτ
These quantiers are interpreted in the following way. The formula ∃τ21 x : ψτis equivalent to ∃x : ((τ1 ≤ x ≤ τ2 ) ∧ ψ) and the formula ∀τ21 x : ψ is equivalent toers.

∀x : ((τ1 ≤ x ≤ τ2 ) → ψ).
The range of the quantied variable is restricted by τ1 and τ2 . Note that these quantiers are not part of our denition of monadic rst-order logic. However, we will showthat all formulas in our logic can be expressed in a special form using these quantiers.
First, we replace all universal quantiers ∀xi : ψ with duals of existential quantiers¬∃xi : ¬ψ . Next, we will convert all quantiers to restricted quantiers and ensure thatthe current formula is always equivalent to the original.
We begin with x1 . There are no variables in the ordering yet and so we replace ∃x1 : ψwith ∃n−1
x1 : ψ , keeping any initial negation. Inductively, we consider xi+1 and have0
existing orderings over the i variables that have already been handled.
39

4.2.

TESTABILITY OF MONADIC FIRST-ORDER LOGIC

40

Let the current formula be ϕ = α(∃xi+1 : ψ), where α denotes the part of the formula
preceding the quantier on xi+1 . We replace γ := (∃xi+1 : ψ) with an equivalent disjunction (γ1 ∨ · · · ∨ γ2i+1 ) of at most 2i + 1 formulas that correspond to the possible neworderings, creating
ϕ0 = α(γ1 ∨ · · · ∨ γ2i+1 ),which is logically equivalent to ϕ.
There are at most i cases where xi+1 is equal to one of the previous variables. These
are handled by letting γj be the formula γ with the quantier ∃xi+1 removed and all
occurrences of xi+1 replaced with xj , for 1 ≤ j ≤ i. Cases where more than two variables
are equal to each other can be easily handled in several ways, for example by renaming
variables or skipping removed quantiers.
By induction, in ϕ there is a xed ordering on the variables that have already beenhandled. For each adjacent pair (α, β) in this ordering we construct a γj that is identicalto the original formula γ except that ∃xi+1 is replaced with ∃β−1
α+1 xi+1 . In addition, wemust add formulas where xi+1 is the smallest variable as well as the largest. Thesen−1formulas are constructed by replacing the quantier with ∃α−1
xi+1 and ∃β+1
xi+1 , where0
α is the minimum and β the maximum element in the ordering. This is at most an
additional i + 1 formulas and the resulting ϕ0 is equivalent to the original formula.
We continue applying the above process until all quantiers have been replaced by
restricted quantiers. At this point we have a (considerably larger) formula such that
there is always an ordering of the variables. It is now simple to determine whether
equality holds between two variables and so we can replace all instances of xi = xj withlogical truth, written >, if i = j and with logical falsehood, written ⊥, otherwise. We
can then make the obvious simplications if desired. The resulting formula satises theprevious conditions and no longer contains equality symbols, which we have replacedwith restricted quantiers and case distinctions.
All predicate symbols are monadic. We move all Ri (x) predicates to their minimumdepth, by which we mean that Ri (x) may occur in the scope of the quantier on x
but must not occur in the scope of any variable whose quantier occurs in the scope ofthat on x. This is done using the following general procedure, which is borrowed from
McNaughton and Papert [33].
Let Ri (xj ) be a relation violating the condition that occurs in the formula. Assume
the formula ϕ is γ∃ττ21 xj : ψ . We replace this withγ∃ττ21 xj : ((Ri (xj ) ∧ ψ1 ) ∨ (¬Ri (xj ) ∧ ψ2 )) .
Here, ψ1 is the result of replacing all occurrences of Ri (xj ) in ψ with >, and ψ2 is theresult of replacing these occurrences with ⊥.
We also want to ensure that all quantied formulas are at their minimum depth. Thisis because we will use the quantier ∃ττ21 x : ψ to construct a regular expression for thepart of the string corresponding to the interval [τ1 , τ2 ], and quantiers that are not at

40

4.2.

TESTABILITY OF MONADIC FIRST-ORDER LOGIC

41

their minimum depth can escape this interval. We use essentially the same process that
we used to move predicate symbols to their minimum depths.
We will consider the quantier ∃ττ21 x : ψ . By construction, there is only one case where
both τ1 and τ2 contain no quantied variables. This is where τ1 = 0 and τ2 = n − 1, andit only occurs at the outermost level. Without loss of generality, we will assume that yis the quantied variable in τ1 = y + 1 and z is the quantied variable in τ2 . We will
also assume that the quantier on y is in the scope of the quantier on z . Cases whereτ1 = 0 or τ2 = n − 1 are similar although only one of these quantied variables exists,and so the minimum depth is immediately within the scope of that variable.
The formula ϕ is4α∃ττ3 zβ∃ττ65 yγ(∃z−1
y+1 x : ψ)ζ.
We move (∃z−1
y+1 x : ψ) to its minimum depth in the same way we moved predicate symbols,
replacing ϕ with
[(
) (
)]
4
z−1
ϕ0 := α∃ττ3 zβ∃ττ65 y : (∃z−1
x
:
ψ)
∧
(γ>ζ)
∨
¬(∃
x
:
ψ)
∧
(γ⊥ζ)
.
y+1
y+1
The quantier on x was the innermost quantier that did not satisfy the new condition, and so all quantiers within ψ are at their minimum depths. There quantiers
z−1
x−1
immediately within ψ are therefore of the form ∃x+1
x1 or ∃y+1
x2 . This is because ourconstruction has ensured that quantiers always range over the interval spanned by adjacent pairs in the ordering. In addition, all variables occurring within ψ are either x
or they are bound by quantiers that occur inside ψ . This is because we have moved
all predicates to their minimum depth. Inductively, ψ depends only on the interval[y + 1, z − 1] and so ϕ0 is logically equivalent to ϕ. If the input is the empty string, then∃z−1
y+1 x : ψ is false by denition and the formula evaluates as it would have. We repeat
the process as necessary.
Finally, we will ensure that in all quantications ϕ = ∃ττ21 x : ψ , the formula ψ is a conjunction over atomic formulas, negated atomic formulas, quantied formulas and negatedquantied formulas. This is simple to do. We begin with the innermost quanticationthat does not satisfy the condition. If we treat quantied formulas as units, we begin by
converting ϕ into disjunctive normal form,

ϕ1 = ∃ττ21 x : (ψ1 ∨ · · · ∨ ψc ) ,where c is the number of clauses. This is equivalent to()()
ϕ0 = ∃ττ21 x : ψ1 ∨ · · · ∨ ∃ττ21 x : ψc .
Each quantied formula is a conjunction and the process is iterated as necessary.
The result we will call a basic formula. These formulas satisfy the following conditions,which will help us construct regular expressions from them.
1. All quantiers are existential.
41

4.2.

TESTABILITY OF MONADIC FIRST-ORDER LOGIC

42

2. All quantied formulas have a xed ordering of the variables and no two variables
are equal to each other.
3. Equality does not occur.
4. All predicate symbols occur at minimum depth. Predicate symbols are the only
way for a variable to appear in these formulas, and so all variables x occur only atminimum depth, omitting their appearance on the restricted quantiers.
5. All quantiers are at their minimum depth.
6. All quantiers are over conjunctions of atomic symbols, negated atomic symbols,
quantied formulas and negated quantied formulas.
We will now show that a regular expression corresponds to each of these formulas.
Recall that the regular expressions are closed under complement, union and intersection.
First, the formula > corresponds to the regular expression Σ∗ and ⊥ to ∅. The regularexpressions are closed under complement, and so the regular expression for ¬φ is thecomplement of the expression for φ.
Next, all quantied formulas are of the form

φ = ∃ττ21 −1+1 x : (α ∧ β ∧ γ),
where α is a conjunction of monadic predicate symbols (and possibly > and ⊥) whose
atomic parts are x, β is a (possibly empty) conjunction of quantied formulas ranging
from τ1 + 1 to x − 1, and γ is a (possibly empty) conjunction of quantied formulas
ranging from x + 1 to τ2 − 1.
There is a (possibly empty) set of characters that correspond to assignments of theRi (x) that model α. If the set is empty, then φ is equivalent to ⊥ and so the regularexpression ∅ corresponds to it. Otherwise, we let C be regular expression formed by theunion of these characters.
By induction we have regular expressions for each of the quantied formulas appearing in β and γ . The regular expression L corresponding to β is formed by taking theintersection of the regular expressions for each of the quantied formulas appearing in
it. The regular expressions are closed under intersection, and so L exists. Likewise,
the regular expression R corresponding to γ is formed by taking the intersection of theregular expressions for each of the quantied formulas appearing in it.
The regular expression corresponding to φ is then the concatenation LCR. This corresponds to the part of the string from positions τ1 + 1 to τ2 − 1.
Finally, disjunctions may appear outside of quantied formulas at the outermost level.
These are disjunctions of quantied formulas ranging from 0 to n − 1 and so the regular expression corresponding to the disjunction is the union of the expressions for theformulas.
The regular languages are closed under intersection, union and complement, and so wehave shown that monadic rst-order logic characterizes a subset of the regular languages.

42

4.3.

ACKERMANN'S CLASS WITH EQUALITY

43

4.3 Ackermann's Class with Equality
In Section 4.1 we reviewed a small portion of the history of the classication problem
for decidability. We found several similarities between the classication for decidability
and the currently known classication for testability. In this section we consider an
additional class, generally referred to as Ackermann's class with equality, and show thisclass to be testable.
In our notation (see Section 2.4), we denote Ackermann's class with equality 2.4)
by [∃∗ ∀∃∗ , all]= . It is the set of sentences containing at most one universal quantier.
Equality and any number of predicate symbols of any arities may occur, but we consider
only pure predicate logic and so there are no function symbols.
Ackermann's class, without equality, was rst shown to be decidable and to have thenite model property by Ackermann [1]. If we also allow equality and one unary function
symbol, the resulting class is Shelah's class. The decidability of this class was proven by
Shelah [41], however it does not have the nite model property.
In Section 4.1 we described similarities between the traditional classication for decidability and the currently known classication for testability. However, all of the decidable
classes mentioned there have the nite model property and so all of the similarities wefound also hold between the classication for the nite model property and the classication for testability. One interesting open problem is therefore to determine whether
Shelah's class is testable. This would require a further generalization of our denitions
to allow function symbols.
Returning to the history of Ackermann's class with equality, Kolaitis and Vardi [29]showed that the satisability problem for the Ackermann class with equality is complete
for NEXPTIME. They also showed that a 0-1 law holds for sentences of existential
second-order logic where the rst-order part belongs to Ackermann's class with equality.
In the absence of equality, Grädel [23] showed that satisability for Ackermann's classis decidable in deterministic exponential time. The main result of Chapter 4 is thetestability of Ackermann's class with equality, which we show in the next section.

4.3.1 Testability of Ackermann's Class with Equality
We would like to assume that the the formulas we consider contain at least one predicate symbol with arity at least two. Therefore, we must treat the remaining cases
specially, which we do now. For formulas that contain no predicate symbols, we cansimply compute ϕ with at most one query. These are therefore trivially testable. Firstorder formulas that contain only monadic predicate symbols characterize a subset of theregular languages and are therefore testable, see Section 4.2. All remaining cases containat least one predicate symbol with arity at least two.
The proof is similar to many of the proofs in Chapter 3. For an arbitrary formulain Ackermann's class with equality, we show that either there are only nitely many

43

4.3.

ACKERMANN'S CLASS WITH EQUALITY

44

structures that are ε-far from having the property dened by the formula, or there are
only nitely many structures that are models of the formula.

Theorem 12. All properties expressible by a formula in [∃∗ ∀∃∗ , all]= are testable.
Let P be the property expressed by an arbitrary formula ϕ in [∃∗ ∀∃∗ , all]= . Then,
we can rename the variables in ϕ so that it takes the following form, where ψ is quantierfree,
Proof.

ϕ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ.
We can further assume that P is a property of structures with vocabulary τ , and wetherefore have s relation symbols Ri of arity ai . We let m := maxi (ai ) be the maximum
arity. The structures in the proof are all implicitly of vocabulary τ .
Either property P holds for at most nitely many structures or it holds for innitely
many. We can trivially test any property that holds for at most nitely many structuresby making the constant number of queries required to determine if the input is exactly
one of the models. Therefore, it remains only to consider the case where ϕ has innitely
many models.
We will show that in this case, there are only nitely many structures A ∈ STRUC (τ )that satisfy dist(A, P ) ≥ ε (cf. Lemma 9). There is therefore a function N (ε) suchthat for any A ∈ STRUC (τ ), if #(A) > N (ε) then the structure A is not ε-far from P .
Therefore, the following is an ε-tester for P on input A with size #(A) = n.
1. If n ≤ N (ε), query all assignments in A and decide exactly whether A has P .
2. Otherwise, accept.
It is worth noting that in the non-uniform case, the N (ε) is simply a constant. It does
depend on the vocabulary, but N (ε) is computable and so P is also uniformly testable.
The proof is complete conditional on Lemma 9, which we show next.

Lemma 9. Let P be the property with vocabulary τ expressed by
ϕ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ
where ψ is quantier free. If ϕ has innitely many models, then there exists an N (ε) for
every ε > 0 satisfying the following. If A ∈ STRUC (τ ) has universe size n > N (ε), thendist(A, P ) < ε.
Let A ∈ STRUC (τ ) be arbitrary and assume it is suciently large. We will showthat there exists an A0 such that A0 |= ϕ (and so A0 has P ) and dist(A, A0 ) < ε.
We begin by showing in Lemma 10 that there must exist a model, A1 , of ϕ such thatthe size of the universe of A1 satises a + 1 ≤ #(A1 ) ≤ κ1 , where()
Ps Paiaiaai −jκ1 := a + 3b a + 2 i=1 j=1 ( j ).
Proof.

44

4.3.

ACKERMANN'S CLASS WITH EQUALITY45

The constant κ1 is determined only by ϕ and does not depend on the input structure.
It is possible to prove tighter bounds on #(A1 ) but this suces for our purposes.
Next, we will show in Lemma 11 that we can easily add additional elements to theuniverse of A1 and construct larger models of ϕ by making only a small number ofmodications. We will then use an inductive argument to show that, for suciently
large input structures A, we can construct A0 |= ϕ where A and A0 have the same
universe size and dist(A, A0 ) < ε.
We now prove the two necessary lemmata.

Lemma 10. If ϕ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb ψ has innitely many models with vocabulary τ , then it has a model A1 such that the cardinality of the universe in A1 satises

a + 1 ≤ #(A1 ) ≤ κ1 .
It suces to consider cases where ϕ has innitely many models with vocabulary τ .
Let B be the smallest5 model of ϕ such that #(B) ≥ a + 1. We are guaranteed that B
exists because there are innitely many models. The proof is by contradiction; assume#(B) > κ1 . We will show that we can construct a smaller6 model of ϕ, violating therequirement that B is the smallest. Therefore, the smallest model of ϕ larger than a + 1
must be of size at most κ1 .
We have chosen B such that it models ϕ, and therefore there exists a tuple of a elements(u1 , . . . , ua ) such that ϕ is satised when the existential quantiers bind these elementsto (x1 , . . . , xa ). If there are multiple possible choices for the xi , we choose one arbitrarily.
We now consider the xi and the substructure induced by them to be xed. We refer tothis substructure as Ax .
Ps Paiaiaai −jmany distinct structures constructed
There are at most κ2 := a + 2 i=1 j=1 ( j )by adding an element labeled y to Ax when we include the structures where the label yis simply placed on one of the xi . We let v ≤ κ2 be the number of such structures that
occur in B and assume there is an enumeration of them.
We know that B models ϕ, and so for each of these v structures there exist b elements,
which we call w1 , . . . , wb , such that when we label wi with zi , the structure induced by(x1 , . . . , xa , y, z1 , . . . , zb ) models ψ . We construct Ai,j for 1 ≤ i ≤ 3 and 1 ≤ j ≤ v suchthat Ai,j is a copy of the w1 , . . . , wb used for the j -th structure in our enumeration. In
each of these cases, we connect the Ai,j to Ax in the same way as in B , by modifying
assignments on tuples (Ax ∪ Ai,j )ak .
For each wh in Ai,j , we must consider the case where y is bound to wh . By construction
the substructure induced by (x1 , . . . , xa , y) occurs in B . We assume that it is the k -th
structure in our enumeration. In this case we will use the elements of Ai+1 mod 3,k toconstruct a structure satisfying ψ . Therefore, we modify the assignments as needed
to create a structure identical to that in B satisfying ψ and claim that the resulting
structure satises ϕ. Before this step we have not modied any assignments spanning
Proof.

5
6

If there are multiple smallest models, choose one arbitrarily.
But still of size at least a + 1.

45

4.3.

46

ACKERMANN'S CLASS WITH EQUALITY

Ax

A1,1

A2,1

A3,1

A1,2

A2,2

A3,2

A1,v

A2,v

A3,v

Figure 4.3.1: Structure A1
the columns of A1 (see Figure 4.3.1) and so there are no assignments that we modify
more than once.
Counting the number of elements, we have at most a + 3bv ≤ a + 3bκ2 = κ1 . If#(A1 ) < a + 1, we can grow it by adding additional columns to A1 in Figure 4.3.1 toconstruct a new A1 satisfying the requirements of the Lemma.
Lemma 10
Our goal is to construct an A0 that has property P by making only a small number ofchanges. We will make the substructure induced by a constant-sized part of A0 equivalent
to the A1 shown to exist above. The size of A1 is upper-bounded by a constant, andso this will require only constantly many modications to assignments. However, wemust also deal with the other elements of A. We will use the following lemma for theseremaining elements.

Lemma 11. Let ϕ = ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb ψ and assume there exists an A |= ϕ, such0that #(A) ≥ a + 1. Then, for any structure A containing A as an induced substructure0
where #(A ) = #(A) + 1, we can construct a model of ϕ by modifying a constant numberof assignments.

A0 contains an induced copy of A and one additional element, which we will denoteby q . By assumption, A is a model of ϕ and therefore contains an a-tuple (u1 , . . . , ua )such that the formula is satised when xi is bound to ui . In addition, the size of A is atleast a + 1, and so it also contains at least one additional element, which we will call p.
We will now make q equivalent to p.
We begin by modifying the assignments necessary to make the structure inducedby (x1 , . . . , xa , q) identical to that induced by (x1 , . . . , xa , p). This requires at most∑s ∑ai (ai ) ai −j= O(1) modications. There must exist (v1 , . . . , vb ) in A such thati=1
j=1 j aψ is satised when zi is bound to vi and y to p. We now modify the assignments
necessary to make the structure induced by (q, v1 , . . . , vb ) identical to that induced
Proof.

46

4.3.

ACKERMANN'S CLASS WITH EQUALITY47∑s ∑ai (ai ) ai −jby (p, v1 , . . . , vb )7 . This requires at most an additional= O(1)
i=1
j=1 j bmodications. The resulting structure has #(A) + 1 elements, models ϕ and was constructed from A0 by making only a constant number of modications to assignments.
Lemma 11
Now, given a suciently large structure A, we will construct A0 by making only alinear8 number of modications, and ensure that A0 |= ϕ.
We begin by selecting arbitrarily #(A1 ) elements and making the induced substructure
identical to the A1 proven to exist in Lemma 10. The size of A1 is constant and therefore
there are at most a constant number of assignments to modify. The A1 from Lemma
10 is of size at least a + 1 and so it satises the conditions of Lemma 11. We proceedinductively: select an element q of A that has not yet been selected. Using Lemma
10, make the substructure induced by the elements selected so far a model of ϕ. Eachstep requires O(1) modications and we require Θ(n) steps. By induction we can thenconstruct A0 from A such that A0 |= ϕ by making at most O(n) modications to theassignments of relations in A.
Then, by denition,O(n)dist(A, A0 ) =< ε.
Θ(nm )The maximum arity is at least two, and so the inequality holds for n suciently large.
This completes the proof of Lemma 9 and therefore that of Theorem 12.
Lemma 97

The case where vi = p can be handled either by assuming it does not occur or by replacing vi withq in (q, v1 , . . . , vb ).
8
Linear in n = #(A).

47

48

Chapter 5Conclusion
In this thesis we have introduced a generalization of property testing which we callrelational property testing. We gave a number of basic results in Chapter 3. In particular,
in Section 3.7 we considered a number of natural alternative denitions of distance andshowed the relationships between the resulting denitions of testability. The denitions
form a strict hierarchy, and the best denition 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 of properties expressible in various syntactic restrictions offormal languages. Finally, a generalization of property testing such as ours is required if
we wish to consider this kind of classication problem.
The second major topic of this thesis is the classication problem for testability, which
we considered in Chapter 4. This problem is inspired by the classical problem for decidability. The major result of Chapter 4 is the testability of Ackermann's class withequality, another example of a similarity between the classication for testability and theclassical one for decidability.

Acknowledgements
I am indebted to my advisor, Prof. Thomas Zeugmann, for his constant encouragement
and advice, which has signicantly improved both my research life and this thesis. I
am very grateful for the support of the Japanese government via a Monbukagakusho
scholarship. Finally, I will always be indebted to my family for their love and support,
and for putting up with me being so far away for so long.

48

49

Bibliography[1] Wilhelm Ackermann. Über die Erfüllbarkeit gewisser Zählausdrücke. Math. Annalen,
100:638649, 1928.
[2] Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Ecient testingof large graphs. Combinatorica, 20(4):451476, 2000.
[3] Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: It's all about regularity. In STOC '06:
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages
251260, New York, NY, USA, 2006. ACM.
[4] Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular
languages are testable with a constant number of queries. SIAM J. Comput.,
30(6):18421862, 2001.
[5] Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties
testable with one-sided error. In Proceedings, 46th Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2005, pages 429438, Washington, DC,
USA, 2005. IEEE Computer Society.
[6] Noga Alon and Asaf Shapira. Homomorphisms in graph property testing. In
M. Klazar, J. Kratochvíl, M. Loebl, J. Matou²ek, R. Thomas, and P. Valtr, editors, Topics in Discrete Mathematics, volume 26 of Algorithms and Combinatorics,
pages 281313. Springer, 2006.
[7] Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties
testable with one-sided error. SIAM J. Comput., 37(6):17031727, 2008.
[8] Noga Alon and Asaf Shapira. A separation theorem in property testing. Combinatorica, 28(3):261281, 2008.
[9] David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity
within NC1. J. of Comput. Syst. Sci., 41(3):274306, 1990.
[10] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting withapplications to numerical problems. J. of Comput. Syst. Sci., 47(3):549595, 1993.
49

50

Bibliography[11] Egon Börger, Erich Grädel, and Yuri Gurevich.
Springer-Verlag, 1997.

The Classical Decision Problem.

[12] J. Richard Büchi. Weak second-order arithmetic and nite-automata.
Logik Grundlagen Math., 6:6692, 1960.

Z. Math.

[13] Hana Chockler and Orna Kupferman. ω -regular languages are testable with a constant number of queries. Theoret. Comput. Sci., 329(1-3):7192, 2004.
[14] Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press, second
edition, 2000.
[15] Eldar Fischer. The art of uninformed decisions. Bulletin of the European Association
for Theoretical Computer Science, 75:97126, October 2001. Columns: Computational Complexity.
[16] Eldar Fischer. Testing graphs for colorability properties. Random Struct. Algorithms,
26(3):289309, 2005.
[17] Rusin² Freivalds. Fast probabilistic algorithms. In Mathematical Foundations ofComputer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia,
September 3-7, 1979, volume 74 of Lecture Notes in Computer Science, pages 5769.

Springer-Verlag, 1979.
[18] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and thepolynomial-time hierarchy. Mathematical Systems Theory, 17(1):1327, 1984.
[19] O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica,
32:302343, 2002.
[20] Oded Goldreich, Sha Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653750, 1998.
[21] Oded Goldreich and Luca Trevisan. Three theorems regarding testing graph properties. Random Struct. Algorithms, 23(1):2357, 2003.
[22] Mira Gonen and Dana Ron. On the benets of adaptivity in property testing of densegraphs. In Moses Charikar, Klaus Jansen, Omer Reingold, and José D.P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques. 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007. Princeton, NJ, USA, August 2007, Proceedings,

volume 4627 of Lecture Notes in Computer Science, pages 525539. Springer, 2007.
[23] Erich Grädel. Satisability of formulae with one ∀ is decidable in exponential time.
Arch. Math. Logic, 29:256276, 1990.
[24] Yuri Gurevich. On the classical decision problem. Bulletin of the European Association for Theoretical Computer Science, pages 140150, October 1990.
50

51

Bibliography[25] J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms.
Transactions of the American Mathematical Society, 117:285306, 1965.
[26] John E. Hopcroft and Jeerey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Adison-Wesley Publishing Company, Reading, Massachusets, USA, 1979.
[27] Juraj Hromkovi£. Design and Analysis of Randomized Algorithms: Introduction to
Design Paradigms. Springer, 2005.
[28] Skip Jordan and Thomas Zeugmann. Indistinguishability and rst-order logic. In
Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, editors, Theory
and Applications of Models of Computation, 5th International Conference, TAMC
2008, Xi'an, China, April 2008, Proceedings, volume 4978 of Lecture Notes in Computer Science, pages 94104. Springer, 2008.

[29] Phokion G. Kolaitis and Moshe Y. Vardi. 0-1 laws and decision problems for fragments of second-order logic. Inf. Comput., 87(1-2):302338, 1990.
[30] K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro. Computability by probabilistic machines. In C.E. Shannon and J. McCarthy, editors, Automata Studies,
pages 183212. Princeton University Press, Princeton, NJ, 1956.
[31] László Lovász. Some mathematics behind graph property testing. In Yoav Freund,László Györ, György Turán, and Thomas Zeugmann, editors, Algorithmic Learning Theory, 19th International Conference, ALT 2008, Budapest, Hungary, October 2008, Proceedings, volume 5254 of Lecture Notes in Computer Science, page 3.

Springer, 2008.
[32] Leopold Löwenheim. Über Möglichkeiten im Relativkalkül. Math. Annalen, 76:447
470, 1915.
[33] Robert McNaughton and Seymour Papert. Counter-Free Automata. M.I.T. Press,
1971.
[34] J. v. Neumann. Zur Theorie der Gesellschaftsspiele. Math. Annalen, 100(1):295320,
1928.
[35] Christos M. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
[36] Michal Parnas and Dana Ron. Testing the diameter of graphs.
Algorithms, 20(2):165183, 2002.

Random Struct.

[37] F. P. Ramsey. On a problem of formal logic. Proc. London Math. Soc. (2), 30:264
286, 1930.

51

Bibliography52[38] Vojt¥ch Rödl and Mathias Schacht. Property testing in hypergraphs and the removal
lemma. In STOC '07: Proceedings of the 39th Annual ACM Symposium on Theoryof Computing, pages 488495, New York, NY, USA, 2007. ACM.
[39] Dana Ron. Property testing. In Sanguthevar Rajasekaran, Panos M. Pardalos,
John H. Reif, and José Rolim, editors, Handbook of Randomized Computing, volume II, chapter 15, pages 597649. Kluwer Academic Publishers, 2001.
[40] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials withapplications to program testing. SIAM J. Comput., 25(2):252271, 1996.
[41] Saharon Shelah. Decidability of a portion of the predicate calculus. Israel J. Math.,28(1-2):3244, 1977.
[42] Stephen Simons. Minimax theorems and their proofs. In Ding-Zhu Du and Panos M.
Pardalos, editors, Minimax and Applications, pages 123. Kluwer Academic Publishers, 1995.
[43] Th. Skolem. Untersuchungen über die Axiome des Klassenkalküls und über Produktations und Summationsprobleme, welche gewisse Klassen von Aussagen betreen. Videnskapsselskapets skrifter, I. Matematisk-naturvidenskabelig klasse, (3):37
71, 1919.
[44] Th. Skolem. Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder
Beweisbarkeit mathematischer Sätze nebst einem Theorem über dichte Mengen. Videnskapsselskapets skrifter, I. Matematisk-naturvidenskabelig klasse, (4):126, 1920.
[45] Howard Straubing.
Birkhäuser, 1994.

Finite Automata, Formal Logic, and Circuit Complexity.

[46] János Surányi. Contributions to the reduction theory of the decision problem: Second paper: Three universal, one existential quantiers. Acta Mathematica Hungarica, 1(24):261271, 1950.
[47] Alfred Tarski. Der Wahrheitsbegri in den formalisierten Sprachen. Studia Philosophica, 1:261405, 1936.
[48] Alfred Tarski. The concept of truth in formalized languages. In Logic, Semantics,
Metamathematics, pages 152278. Oxford University Press, Oxford, 1956.
[49] Andrew Chi-Chih Yao. Probabilistic computations: Toward a unied measure ofcomplexity. In 18th Annual Symposium on Foundations of Computer Science, pages
222227. IEEE Computer Society, 1977.

52