Regular Languages are Testable with a Constant Number of Queries.
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750]. The subject of this paper is testing regular languages. Our main result is as follows. For a regular language $L\in \{0,1\}^*$ and an integer n there exists a randomized algorithm which always accepts a word w of length n if $w\in L$ and rejects it with high probability if $w$ has to be modified in at least $\epsilon n$ positions to create a word in L. The algorithm queries $\tilde{O}(1/\epsilon)$ bits of w. This query complexity is shown to be optimal up to  a factor polylogarithmic in $1/\epsilon$. We also discuss the testability of more complex languages and show, in particular, that the query complexity required for testing context-free languages cannot be bounded by any function of $\epsilon$. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.
Introduction
Property testing deals with the question of deciding whether a given input x satises a prescribed
property P or is \far" from any input satisfying it. Let P be a property, i.e. a non-empty family of
binary words. A word w of length n is called -far from satisfying P , if no word w 0 of the same length,
which diers from w in no more than n places, satises P . An -test for P is a randomized algorithm,
which given the quantity n and the ability to make queries about the value of any desired bit of an
input word w of length n, distinguishes with probability at least 2=3 between the case of w 2 P and
A preliminary version of this paper appeared in the Proceedings of the 40 th Symposium on Foundation of Computer
Science
y Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv
69978, Israel, and AT&T Labs{Research, Florham Park, NJ 07932, USA. Email: noga@math.tau.ac.il. Research supported
by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center
for Geometry at Tel Aviv University.
z Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv
69978, Israel. E-mail: krivelev@math.tau.ac.il Part of this research was performed when this author was with DIMACS
Center, Rutgers University, Piscataway NJ, 08854, USA and AT&T Labs{Research, Florham Park, NJ 07932, USA.
Research supported in part by a DIMACS Postdoctoral Fellowship.
x Department of Computer Science, University of Haifa, Haifa, Israel. E-mail: ilan@cs.haifa.ac.il. Part of this research
was performed when this author was visiting AT& T Labs { Research, Florham Park, NJ 07932, USA.
{ School of Mathematics, Institute for Advanced Study, Olden Lane, Princeton, NJ 08540, USA. E-mail:
szegedy@math.ias.edu. Part of this research was performed when this author was with AT&T Labs{Research, Florham
Park, NJ 07932, USA.
the case of w being -far from satisfying P . Finally, we say that property P is (c; )-testable if for every
> 0 there exists an -test for P whose total number of queries is bounded by c.
Property testing was dened by Goldreich et. al [7] (inspired by [13]). It emerges naturally in
the context of PAC learning, program checking [6, 3, 10, 13], probabilistically checkable proofs [2] and
approximation algorithms [7].
In [7], the authors mainly consider graph properties, such as bipartiteness and show (among other
things) the quite surprising fact that testing bipartiteness can be done by randomly testing a polynomial
in 1= number of edges of the graph, answering the above question with constant probability of failure.
They also raise the question of obtaining general results as to when there is, for every  > 0, an -test
for a property using queries (i.e c is a function of  but independent of n) with constant
probability of failure. We call properties of this type -testable. So far, such answers are quite sparse;
some interesting examples are given in [7], several additional ones can be obtained by applying the
Regularity Lemma as we show in a subsequent paper [1].
In this paper we address testability of formal languages (see [8] as a general reference). A language
is a property which is usually viewed as a sequence of Boolean functions f
Our main result states that all regular languages are -testable with
query complexity only ~
O(1=). We also show that this complexity is optimal up to a factor poly-logarithmic
in 1=. This positive result cannot be extended to context-free languages, for there is an
example of a very simple context-free language which is not testable.
Since regular languages can be characterized using second order monadic logic, we thus obtain a
large set of logically dened objects which are testable. In [1] we provide testable graph properties
described by logical means as well. These results indicate a strong interrelation between testability and
logic. Although our result on regular languages can be viewed as a separate result having no logical
bearing at all, our opinion is that logic does provide the right context for testability problems, which
may lead to the discovery of further classes of testable properties.
The rest of this paper is organized as follows. In Section 2 we present the proof of the main result
showing that every regular language is testable. In Section 3 we show that the upper bound of ~
O(1=)
for the query complexity of testing regular languages, obtained in Theorem 1, is tight up to a poly-logarithmic
factor. Section 4 is devoted to the discussion of testability of context-free languages. There
we show in particular that there exist non-testable context-free languages. We also discuss testability
of the Dyck languages. The nal Section 5 contains some concluding remarks and outlines new research
directions.
Testing Regular Languages
In this section we prove the main result of the paper, namely that regular languages are ( ~
O( 1
testable. As this result is asymptotic, we assume that n is big enough with respect to 1
(and with
respect to any other constant that depends only on the xed language we are working with). All
logarithms are binary unless stated explicitly otherwise.
We start by recalling the standard denition of a regular language, based on nite automata. This
denition is convenient for algorithmic purposes.
Denition 2.1 A deterministic nite automaton (DFA) M over f0; 1g with states
is given by a function with a set F  Q. One of the states, q 1 is called
the initial state. The states belonging to the set F are called accepting states, - is called the transition
function.
We can extend the transition function - to f0; 1g  recursively as follows. Let
denote the empty
word. Then
Thus, if M starts in a state q and processes string u, then it ends up in a state -(q; u).
We then say that M accepts a word u if -(q rejects u means that -(q 1
Finally, the language accepted by M , denoted by LM , is the set of all u 2 f0; 1g  accepted by M . We
use the following denition of regular languages:
Denition 2.2 A language is regular i there exists a nite automaton that accepts it.
Therefore, we assume in this section that a regular language L is given by its automaton M so that
A word w of length n denes a sequence of states (q
) in the following natural way: q
and for 1  j  n,
This sequence describes how the automaton M moves while
reading w. Later in the paper we will occasionally refer to this sequence as the traversal path of w.
A nite automaton M denes a directed graph G(M) by V
g. The period g(G) of a directed graph G is the greatest common
divisor of cycle lengths in G. If G is acyclic, we set
We will use the following lemma about directed graphs.
Lemma 2.3 Let E) be a nonempty, strongly connected directed graph with a nite period g(G).
Then there exist a partition V which does not exceed 3jV j 2
such
1. For every 0  1 and for every the length of every directed path from u to
v in G is (j i) mod
2. For every 0  1 and for every and for every integer r  m, if
(mod g), then there exists a directed path from u to v in G of length r.
Proof. To prove part 1, x an arbitrary vertex z 2 V and for each 0  i  g 1, let V i be the set
of all those vertices which are reachable from v by a directed, (not necessarily simple), path of length
g. Note that since any closed (directed) walk in G is a disjoint union of cycles, the length of each
such walk is divisible by g. This implies that the sets V i are pairwise disjoint. Indeed, assume this is
false and suppose w lies in V i \ V j with i 6= j. As G is strongly connected there is a path p 1 from w
to z, and by denition there is a path p 2 of length i mod g from z to w as well as a path p 3 of length
mod g from z to w. Now the number of edges of either 3 is not divisible by g, which
is impossible. Therefore the sets V i form, indeed, a partition of V . For the union
of any (directed) path from z to u with a (directed) path from u to v forms a path from z to v, and as
any such path must have length j mod g the assertion of part 1 follows.
We next prove part 2. Consider any set of positive integers fa i g whose greatest common divisor is g.
It is well known that there is a smallest number t such that every integer s  t which is divisible by g
is a linear combination with non-negative integer coe-cients of the numbers a i . Moreover, it is known
(see [9], [5]), that t is smaller than the square of the maximal number a i . Fix a closed (directed) walk
in G, that visits all vertices and whose length is at most jV j 2 . (This is easily obtained by numbering
the vertices of G arbitrarily as by concatenating directed paths from v i to v i+1 for
each 0  i  k 1, where the indices are taken modulo k). Associate now the set of cycle lengths in
this walk with the set of positive integers fa i g as above. Then, following this closed walk and traversing
each directed cycle as many times as desired, we conclude that every integer which is divisible by g and
exceeds 2jV j 2 is a length of a closed walk passing through all vertices of the graph. Given, now, a vertex
and an integer r > 3jV (j i) mod g, x a shortest path p from
u to v, and note that its length l satises l = (j i) mod g and l < jV j( jV j 2 ). Adding to p a closed
walk of length r l from v to itself we obtain the required path, completing the proof. 2
We call the constant m from the above lemma the reachability constant of G and denote it by m(G).
In the sequel we assume that m is divisible by g.
If LM \ f0; 1g testing algorithm can reject any input without reading it at all. Therefore,
we can assume that we are in the non-trivial case LM \ f0; 1g n 6= ;.
We now introduce a key denition for the sequel:
Denition 2.4 Given a word w 2 f0; 1g n , a sub-word (run) w 0 of w starting at position i is called
feasible for language LM , if there exists a state q 2 Q such that q is reachable from q 1 in G in exactly
steps and there is a path of length n (jw in G from the state -(q; w 0 ) to at least one of
the accepting states. Otherwise, w 0 is called
Of course, nding an infeasible run in w proves that w 62 L. Our aim is to show that if a given word
w of length n is far from any word of length n in L, then many short runs of w are infeasible. Thus a
choice of a small number of random runs of w almost surely contains an infeasible run. First we treat
the following basic case:
Denition 2.5 We call an automaton M 'essentially strongly connected' if
1. M has a unique accepting state q acc ;
2. The set of states of the automaton, Q, can be partitioned into two parts, C and D so that
the subgraph of G(M) induced on C is strongly connected;
no edges in G(M) go from D to C (but edges can go from C to D).
(Note that D may be empty.)
Lemma 2.6 Assume that the language contains some words of length n, and that M is
essentially strongly connected with C and D being the partition of the states of M as in Denition 2.5.
Let m be the reachability constant of G[C]. Assume also that n  64m log(4m=). Then if for a word
w of length exists an integer 1  i  log(4m=) such that the
number of infeasible runs of w of length 2 i+1 is at least 2 i 4 n
Proof.
Our intention is to construct a sequence (R j ) j=1;::: of disjoint infeasible runs, each being minimal in
the sense that each of its prexes is feasible, and so that each is a subword of the given word w. We
then show that we can concatenate these subwords to form a word in the language that is not too far
from w ('not too far' will essentially depend on the number of runs that we have constructed). This
in turn will show that if dist(w; L)  n then there is a lower bound on the number of these infeasible
runs.
For reasons to become obvious later we also want these runs to be in the interval [m
A natural way to construct such a sequence is to repeat the following procedure starting from
1 be the shortest infeasible run starting from w[m + 1] and ending before
there is no such run we stop. Assume that we have constructed so
ending at w[c j 1 ], next we construct R j by taking the minimal infeasible run starting at w[c
and ending before w[n m+ 1]. Again if there is no such run we stop.
Assume we have constructed in this way runs R 1 ; :::; R h . Note that each run is a subword of w,
the runs are pairwise disjoint and their concatenation in order forms a (continuous) subword of w.
Also, note that by the denition of each run R j being minimal infeasible, its prex R (
obtained by
discarding the last bit of R j is feasible. This, in turn, implies that R 0
j which is obtained from R j by
ipping its last bit is feasible. In addition, by Denition 2.4, this means that for each R 0
there is a state
and such that q i j
is reachable from q 1 in c
Next we inductively construct a word w  2 L such that dist(w; w  )  hm+ 2m+ 2. Assuming that
dist(w; L)  n this will imply a lower bound on h. The general idea is to 'glue' together the R 0
h, each being feasible and yet very close to a subword of w (except for the last bit in each).
The only concern is to glue the pieces together so that as a whole word it will be feasible. This will
require an extra change of m bits per run, plus some additional 2m bits at the end of the word.
We maintain during the induction that for we construct is feasible starting
from position 1, and it ends in position c j . For the base case, let c to be any word of
length m which is feasible starting from position 1. Assume we have already dened a word w
from position 1 and ending in position c j 1 . Let -(q As both p j and q i j
are reachable
from q 1 by a path of length c j 1 , according to Lemma 2.3 we can change the last m bits in w j 1 so
that we get a word u j for which -(q 1 ;
. We now dene w j as a concatenation of u j and R 0
. Let
w h be the nal word that is dened in this way, ending at place c h . Now the reason we have stopped
with R h is either that there is no infeasible run starting at c h + 1, in which case, changing the last m
bits of w h and concatenating to it the remaining su-x of w (that starts at position c h exactly as
in the case of adding R 0
yields the required w  . The other possible reason for stopping growing R h is
when there is a minimal infeasible run that start at c h ends after position n m+ 1. Let R be
that run, and let R 0 be the run obtained by
ipping the last bit of R. As was the case with any R 0
is feasible from position c h + 1. Hence there is a feasible word u of which R 0 is a prex, u is of length
and so that -(q i h
. We can construct w  from w h and u exactly as we have constructed
w  form w h and the su-x of w in the previous case.
By the denition of w  , w  2 L. Following the inductive construction of w  it follows that for
1. Then to get from w h to w  we concatenate R 0 which is either a
subword of w (in the rst case previously discussed) or it is a subword of w where one bit was changed
(in the second case), following by changing m bits at the end of w h and possibly additional m bits at
the end of u. Therefore dist(w; w  )  hm 2, as we claimed.
Recalling that dist(w; L)  n, we conclude that h  n 2
last inequality is
by our assumptions that n  64m log(4m=)). This already shows that if dist(w; L)  n then there
are
n) many disjoint infeasible runs in w. However, we need a stronger dependence as stated in the
lemma. We achieve this in the following way.
Let log(4m=). For 1  i  a, denote by s i the number of runs in fR j g h
whose length
falls in the interval [2
P a
h n=(4m)  n=(4m). Therefore there exists an index i for which s i  n=(4am). Consider all
infeasible runs R j with jR that if a run contains an infeasible sub-run then it is
infeasible by itself. Now, each infeasible run of length between 2 contained in at least
runs of length 2 i+1 , except maybe, for the rst two and the last two runs (these with the
two smallest j's and these with the two largest j's). As R j are disjoint, each infeasible run of length
contains at most three of the R j s of length at least 2 1. Thus, we a get a total of at least
runs of length at most 2 i+1 . By our assumption on the parameters this number
is:
am
log(4m=) , as claimed. 2
Now our aim is to reduce the general case to the above described case. For a given DFA M with
a graph by C(G) the graph of components of G, whose vertices correspond to
maximalby inclusion strongly connected components of G and whose directed edges connect components
of G, which are connected by some edge in G. Note that some of the vertices of C(G) may represent
single vertices of G with no self loops, that do not belong to any strongly connected subgraph of G
with at least two vertices. All other components have non empty paths inside them and will be called
truly connected. From now on we reserve k for the number of vertices of C(G) and set
may assume that all vertices of G are reachable from the initial state q 1 . Then C(G) is an acyclic graph
in which there exists a directed path from a component C 1 , containing q 1 , to every other component.
runs over all truly connected components
of G, corresponding to vertices of C(G). We will assume in the sequel that the following relation are
satised between the parameters:
Condition (*)
2k  64m log 8mk
.
log(1=) < 1
clearly, for any xed k; m; l for  small enough and n large enough condition (*) holds.
Our next step is to describe how a word w 2 LM of length n can move along the automaton. If a word
w belongs to L, it traverses G starting from q 1 and ending in one of the accepting states. Accordingly,
w traverses C(G) starting from C 1 and ending in a component containing an accepting state. For
this reason, we call a path A in C(G) admissible, if it starts at C 1 and ends at a component with an
accepting state. Given an admissible path
in C(G), a sequence
of
pairs of vertices of G (states of M) is called an admissible sequence of portals if it satises the following
restrictions:
1.
for every 1  j  t;
2.
3.
t is an accepting state of M );
4. For every 2  j  t one has (p 2
The idea behind the above denition of admissible portals is simple: Given an admissible path A,
an admissible sequence P of portals denes how a word w 2 L moves from one strongly connected
component of A to the next one, starting from the initial state q 1 and ending in an accepting state. The
are the rst and last states that are traversed in C i j
Now, given an admissible path A and a corresponding admissible sequence P of portals, we say that
an increasing sequence of integers
forms an admissible partition with respect to (A; P ) if
the following holds:
1.
2. for every 1  j  t, there exists a path from p 1
j to p 2
of length n j+1
3.
The meaning of the partition
j=1 is as follows. If w 2 L and w traverses M in accordance
with t, the value of n j indicates that w arrives to component C
for
the rst time after n j bits. For convenience we also set n 1. Thus, for each 1  j  t, the
word w stays in C i j
in the interval [n that it is possible in principle that for a
given admissible path A and a corresponding admissible sequence of portals P there is no corresponding
admissible partition  (this could happen if the path A and the set of portals P correspond to no word
of length n).
A triplet (A; is an admissible path, P is a corresponding admissible sequence of
portals and  is a corresponding admissible partition, will be called an admissible triplet. It is clear
from the denition of an admissible triplet that a word w 2 L traverses G in accordance with a scenario
suggested by one of the admissible triplets. Therefore, in order to get convinced that w 62 L, it is enough
to check that w does not t any admissible triplet.
Fix an admissible triplet (A;
. For
t, we dene a language L j that contains all words that traverse in M from p 1
j to p 2
. This is
done formally by dening an automaton M j as follows: The set of states of M j is obtained by adding to
a new state f j . The initial state of M j and its unique accepting state are p 1
respectively. For
each
and  2 f0; 1g, if - M (q;
, we set - M j
We
Namely, in M j all transitions within C
remain the same.
All transitions going to other components now go to f j which has a loop to itself. Thus, M j is essentially
strongly connected as in Denition 2.5 with g. Then L j is the language accepted by M j .
Given the xed admissible triplet (A; word w of length sub-words of
setting t. Note that jw
Namely, if w were to path through M according to the partition  then the substring w j corresponds
to the portion of the traversal path of w that lies within the component C
Lemma 2.7 Let (A; be an admissible triplet , where
. Let w be a word of length n satisfying dist(w; L)  n. Dene languages (L
and words
(w
as described above. Then there exists an index j, 1  j  t, for which dist(w
k .
Proof. Assume this is not the case. Let
j=1 be the partition and recall that t  k. For
every be a word of length n j+1 n j 1 for which
(the empty word). Also, for 1  j  t 1
choose  j 2 f0; 1g so that - M (p 2
j+1 . Then by construction the word w
belongs to L and dist(w; w
{ a contradiction.Now we present a key idea of the proof. Ideally, we would like to test whether an input word w
of length n ts any admissible triplet. In the positive case, i.e. when w 2 LM , the traversal path of
w in M denes naturally an admissible triplet which w will obviously t. In the negative case, i.e.
when dist(w; L)  n, Lemma 2.7 implies that for every admissible triplet (A; P; ), at least one of the
sub-words w j is very far from the corresponding language L j . Then by Lemma 2.6 w j contains many
short infeasible runs, and thus sampling a small number of random runs will catch one of them with
high probability. However, the problem is that the total number of admissible triplets clearly depends
on n, which makes the task of applying directly the union bound on the probability of not catching an
infeasible run impossible.
We circumvent this di-culty in the following way. We place evenly in a bounded number
(depending only on  and the parameters of M) of transition intervals T s of a bounded length and
postulate that a transition between components of C(G) should happen inside these transition intervals.
Then we show that if w 2 L, it can be modied slightly to meet this restriction, whereas if dist(w; L)
n, for any choice of such an admissible triplet, w is far from tting it. As the number of admissible
triplets under consideration is bounded by a function of  only, we can apply the union bound to estimate
the probability of failure.
Recall that runs over all truly connected components
of G, corresponding to vertices of C(G). Let log(1=)=. We place S transition intervals
s=1 evenly in [n], where the length of each transition interval T s is jT s m).
For
.
ALGORITHM
Input: a word w of length
1. For each 1  i  log(8km=) choose r i random runs in w of length 2 i+1
2. For each admissible triplet (A;
j=1 such
that for all 2  j  t one has do the following:
Form the automata M j , 1  j  t, as described above.
Discard those chosen runs which end or begin at place p for which jp n j j  n=(128km log(1=)).
Namely, those runs which have one of their ends closer than n=(128km log(1=)) from some
For each remaining run R, if R falls between n j and n j+1 , check whether it is feasible for
the automaton M j starting at b n is the rst coordinate of R in w. Namely,
is the place where R starts relative to n j , which is the the place w \enters" M j .
3. If for some admissible triplet all checked runs turned out to be feasible, output "YES". Otherwise
(i.e, in the case where for all admissible triplets at least one infeasible run has been found) output
"NO".
Lemma 2.8 If dist(w; L)  n, then the above algorithm outputs "NO" with probability at least 3=4.
If w 2 L, then the algorithm always outputs "YES".
Proof. The proof contains two independent parts, in the rst we consider the case of an input w with
dist(w; L)  n, on which the algorithm should answer 'NO' (with high probability). The other part
treats the case where w 2 L, for which the algorithm should answer 'YES'.
Let us rst assume that dist(w; L)  n. The number of admissible triplets (A;
partition points fall into the union of transition intervals
can be estimated from above by
(rst choose an admissible path in C(G), the number of admissible paths is at most 2 k as any subset of
vertices of C(G) denes at most one path spanning it; then choose portals, the total number of chosen
portals is at most 2k, therefore there are at most jV j 2k possible choices for portals; then for a xed
there are at most SjT s j choices for each n j , where 2  j  t and t  k). For  satisfying
condition (*) and S as above, this expression is at most (1=) 2k . Thus we need to check at most (1=) 2k
admissible triplets.
Let be an admissible triplet satisfying the restriction formulated in Step 2 of the above
algorithm. Write
. Then the triplet denes automata
and languages (L
as described before. By Lemma 2.7 for some 1  j  t one has
n=(2k). Then by Lemma 2.6 there exists an i, 1  i  log(8km=) so that
contains at least (2 i 4 n=(2km log(8km=))  runs of length 2 i+1 . At
most of them may touch the last  bits of the interval [n 1], and at most
of them may touch the rst  bits of this interval. Hence there are at least 2 i 6 n=(km log(1=)) 2
of them that touch neither the rst nor the last n=(128km log(1=)) bits of the
interval Obviously, if a random sample contains one of these infeasible runs, then it
provides a certicate for the fact that w does not t this admissible triplet. A random sample of r i runs
of length 2 i+1 misses all of these infeasible runs with probability at most

2k
Thus by the union bound we conclude that in this case a random sample does not contain a "witness" for
each feasible triplet with probability at most 1=4. This completes the proof for the case of dist(w; L)
n.
We now address the case for which w 2 L. We need to show that in this case the algorithm answers
'YES'. For this is is enough to show that if w 2 L, then there exists an admissible triplet which passes
successfully the test of the above algorithm. A traversal of w in M naturally denes a triplet (A;
as follows:
are components from C(G), ordered according to the
order of their traversal by w;
is the rst (resp. the last) state of C
visited by w;
set to be the rst time w
enters
while traversing M . However, this partition does not necessarily meet the requirement stated
in Step 2 of the algorithm: In the true traversal of w in M the transitions from C i j
to C i j+1
might
occur outside the transition intervals T s . We show that the desired triplet can be obtained from the
actual triplet, modifying only the third component of it. This modied triplet would
then correspond to a dierent word w (which is quite close to w) that makes all the transitions
inside the postulated transition intervals. In addition, we will take care that no query is made to bits
in which w 0 diers from w. Hence, the algorithm will actually be consistent with both. This is in fact
the reason for discarding the runs that are too close to some n j in Step 2 of the algorithm. Intuitively,
this is done as follows: Assume n j is not in a transition interval, then we either make the traversal in
longer so to end in p 2
in a transition interval, or we shorten the traversal in C so to enter
a transition interval, depending on where the closest transition interval is. Formally this is done as
follows. Dene a new partition
choose a transition
interval T s closest to n j . If C
is a truly connected component, we choose n 0
j as the leftmost coordinate
in T s satisfying the following restrictions: (a) n 0
is a singleton
without loops we set n 0
such an n 0
exists. Finally, we set
Note that the obtained triplet (A;
is truly connected. As there
exists a path from p 1
j to p 2
of length n j+1 n j 1, there also exists a path of length n 0
j 1.
This implies the admissibility of  0 and hence the admissibility of (A;
Let now R be a run of w inside [n 0
j+1 n=(128km log(1=))] and let b be its
rst coordinate. Since we placed S transition intervals fT s g evenly in [n], we have jn 0
+m). Therefore, R falls also completely inside [n
remark at this point that the purpose of discarding marginal runs at Step 2 of the algorithm is to achieve
that each one of the remaining runs will fall completely not only within [n 0
j+1 ], but also within
As we will see immediately this guarantees that R will be feasible for the corresponding
automaton M j . Without this deletion, with positive probability one of the sampled runs R may start in
a place where w is in C
and end in a place where w is in C i j
, thus making it impossible to attribute
R to one particular automaton M j . Therefore, with positive probability the algorithm would fail in the
positive case. Discarding marginal runs allows us to get a one-sided error algorithm).
As w 2 L, there exists a state q 2 C
so that -(q; R) 2 C
. Also, q is reachable from p 1
(the initial
state of C
steps (b is the rst coordinate of R). According to the choice of n 0
j we
have
is the period of C
. But then by Lemma 2.3 q is reachable from p 1
in
m) steps. This shows that R is feasible for M j , starting at b n 0
1. Thus, if w 2 L, the
above algorithm always outputs "YES". 2
Finally, the number of bits of w queried by our algorithm is at most
log(8km=) X
log(8km=) X
We have thus proven the following theorem.
Theorem 1 For every regular language L, every integer n and every small enough  > 0, there exists
a one-sided error -testing algorithm for L\ f0; 1g n , whose query complexity is c log 3 (1=)=, where the
constant c > 0 depends only on L.
A nal note about the dependence of the complexity on the parameters is in place here. In the proof
M is considered xed, as the algorithm is tailored for a xed given language. However, in the calculation
above we have kept the dependence of the query complexity on the parameters of M explicit. One has
to take in mind though that the estimates hold only when condition (*) holds. In particular we require
(third item in (*)), that 1=(
Another note is about the running time of the algorithm (rather then just its query complexity). The
dominating term in Step 1 and the rst two subsets of Step 2 of the algorithm is the query complexity.
In the last substeps, each run has to be checked against M j . Each such check involves checking whether
there is a word u and a word v (of suitable lengths) so that uRv 2 L. Checking whether there are such
u; v is done directly by Lemma 2.3 in case the length of u and v are longer than m, or by checking all
words if one of them is shorter than m.
3 Lower bound for regular languages
In many testability questions, it is quite natural to expect a lower bound of order 1= for the query
complexity of testing. This is usually proven by taking a positive example of size n and perturbing it in
randomly chosen n places to create a negative instance which is hard to distinguish from the positive
one. Regular languages are not an exception in this respect, as shown by the next proposition and its
fairly simple proof.
Proposition 1 Let L be the regular language over the alphabet f0; 1g dened by 1g. For
any n an -test for L \ f0; 1g n has query complexity at least 1
3 .
Proof. Our proof is based on the following reformulation of the renowned principle of Yao [14], saying
that if there exists a probability distribution on the
union
of positive and negative examples such that
any deterministic testing algorithm of query complexity d is correct with probability less than 2/3 for
an input randomly chosen
from
according to this distribution, then d is a lower bound on the query
complexity of any randomized testing algorithm.
Dene a distribution on the set of positive and negative instances of length n as follows. The word
gets probability 1=2. Next we partition the index set [1; n] into , each of size
n, and for each 1  i  t give probability 1=(2t) to the vector y i created from 1 n by
ipping all bits in
I i from 1 to 0. Note that dist(y are negative instances. Now we apply the above
mentioned principle of Yao. Let A be a deterministic -testing algorithm with query complexity d. If
A is incorrect on the word 1 n , then it is already incorrect with probability at least 1=2. Otherwise, it
should accept the input if all d tested bits equal to 1. Therefore it accepts as well at least t d of the
inputs y i . This shows that A gives an incorrect answer with probability at least (t d)=(2t) < 1=3,
implying d > t=3. 2.
The main idea of the proof of the above proposition can be used to get an
=) lower bound on
the query complexity of testing any non-trivial regular language, with a natural denition of non-trivial.
This is proven in the next proposition. A somewhat paradoxical feature of its proof is that our main
positive result (Theorem 1) and its proof are used here to get a negative result.
For a language L let L
Denition 3.1 A language L is non-trivial if there exists a constant 0 <  0 < 1, so that for innitely
many values of n the set L n is non-empty, and there exists a word w 2 f0; 1g n so that dist(w; L n )   0 n.
Proposition 2 Let L be a non-trivial regular language. Then for all su-ciently small  > 0, any
-testing algorithm for L requires
queries.
Proof. The proof here is essentially a generalization of the proof of Proposition 1. We thus present it
in a somewhat abridged form.
Let n be large enough. Assume L n 6= ;, and w 2 f0; 1g n is such that dist(w; L n )   0 n. We may
clearly assume that the constant  0 is as small as needed for our purposes. Our main result, Theorem
1, and its proof imply that with probability at least 2=3, a random choice of a set of runs, built as
described at Step 1 of the testing algorithm of Theorem 1, and having total length ~
the algorithm to reject w. As we have noticed, the testing algorithm has one sided error, i.e., it always
accepts a word from L. Thus, if we choose a random set of runs as above, it will cause to reject w with
probability 2/3 and it will not coincide with any word u 2 L n (for otherwise, it would reject u too).
Each such random set of runs is just a random set of intervals in ng (of length as dened in
Step 1 of the testing algorithm) of total length bounded by ~
that two such random sets
intersect with probability ~
n)). Therefore if we choose ~
n) such subsets at random, then we
expect that ~
O( 2
n) pairs of them will intersect, and that 2/3 of the members will reject w. This implies
that there exists a family S of ~
disjoint sets of runs so that for each member of S, no
word of L n coincides with w on this set. Fix now  0 and let  > 0 be small enough compared to  0 . We
partition the family S into , each of cardinality n, where the constant c
depends on  0 only and is thus independent of . Let u be a word in L n . For each 1  i  t, the word
w i is obtained from u by changing the bits of u, corresponding to S i , to those from w. It follows then
that Indeed, to transform w i into a word in L n , at least one bit has to be changed
in every member of S i .
Now, as in the proof of Proposition 1, we dene a probability distribution on the union of positive
and negative examples. The word u gets probability 1=2, and each one of the t words w
probability 1=(2t). A simple argument, essentially identical to that in the proof of Proposition 1, shows
that any deterministic algorithm needs to query at
least
3 =) bits of the input word to be
successful with probability at least 2=3 on the dened probability distribution. Applying Yao's principle,
we get the desired result. 2
4 Testability of context-free languages
Having essentially completed the analysis of testability of regular languages, it is quite natural to try
to make one step further and to address testability of the much more complex class of context-free
languages (see, e.g., [8] for a background information). It turns out that the general situation changes
drastically here as compared to the case of regular languages. We show that there exist quite simple
context-free languages which are not -testable. Then we turn our attention to one particular family of
context-free languages { the so-called Dyck languages. We prove that the rst language in this family,
testable in time polynomial in 1=, while all other languages in the family are already non-testable.
All relevant denitions and proofs follow.
4.1 Some context-free languages are non-testable
As we have already mentioned, not all context-free languages are testable. This is proven in the following
proposition.
Theorem 2 Any -testing algorithm for the context-free language
the reversal of a word w, requires
n) queries in order to have error of at most 1=3.
Proof. Let n be divisible by 6. We again dene a distribution D on the union of positive and negative
inputs in the following way. A negative instance is chosen uniformly at random from among all negative
instances (i.e. those words w 2 f0; 1g n which are at distance at least n from L). We refer to this
distribution as N . Positive instances are generated according to a distribution P dened as follows: we
pick uniformly at random an integer k in the interval [n=6 and then select a positive example
uniformly among words vv R uu R with k. Finally the distribution D on all inputs is dened as
follows: with probability 1/2 we choose a positive input according to P and with probability 1=2 we
choose a negative input according to N . We note that a positive instance is actually a pair (k; w) (the
same word w may be generated using dierent k's).
We use the above mentioned Yao's principle again. Let A be a deterministic -testing algorithm for
L. We show that for any such A, if its maximum number of queries is
n), then its expected
error with respect to D is at least 1
A be such an algorithm. We can view A as
a binary decision tree, where each node represents a query to a certain place, and the two outgoing
edges, labeled with 0 or 1, represent possible answers. Each leaf of A represents the end of a possible
computation, and is labeled 'positive' or `negative' according to the decision of the algorithm. Tracing
the path from the root to a node of A, we can associate with each node t of A a pair (Q t
ng is a set of queries to the input word, and f is a vector of answers received
by the algorithm. We may obviously assume that A is a full binary tree of height d and has thus 2 d
leaves. Then jQ for each leaf t of A.
We will use the following notation. For a subset Q ng and a function f
with f on Qg ;
with f on Qg ;
is the set of all negative (resp. positive) instances of length n consistent with
the pair (Q; f ). Also, if D is a probability distribution on the set of binary strings of length n and
is a subset, we dene Pr D
w2E Pr D [w].
be the set of all leaves of A labeled 'positive', let T 0 be the set of all leaves of T labeled
'negative'. Then the total error of the algorithm A on the distribution D is
Pr
The theorem follows from the following two claims.
4.1 For every subset Q ng of cardinality
Pr D [E (Q; f )]
4.2 For every subset Q ng of cardinality
n) and for every function f
Pr
Based on Claims 4.1, 4.2, we can estimate the error of the algorithm A by
Pr
The theorem follows. 2
We now present the proofs of Claims 4.1 and 4.2.
Proof of Claim 4.1: Notice rst that L has at most 2 n=2 n=2 words of length n (rst choose a word
of length n=2 and then cut it into two parts v and u, thus getting a word
the number of words of length n at distance less than n from L is at most jL \ f0; 1g n j
log(1=)n . We get
It follows then from the denition of D that
Pr D [E (Q; f
Proof of Claim 4.2: It follows from the denition of the distribution D that for a word w 2 L\f0; 1g n ,
Pr D
Recall that f) is the set of words in L for which are consistent with f on the set of queries Q,
Hence,
Pr
Now observe that for each of the d pairs of places in Q there are at most two choices of k, for which
the pair is symmetric with respect to k or to n=2 + k. This implies that for n=6 2
choices of k, the set Q does not contain a pair symmetric with respect to k or n=2+k. For each such k,
Therefore,
Pr
As a concluding remark to this subsection we would like to note that in the next subsection (Theorem
we will give another proof to the fact that not all context-free languages are testable by showing
the non-testability of the Dyck language D 2 . However, we preferred to give Theorem 2 as well due to
the following reasons. First, the language discussed in Theorem 2 is simpler and more natural than
the Dyck language D 2 . Secondly, the lower bound of Theorem 2 is better than that of Theorem 4.
The proofs of these two theorems have many common points, so the reader may view Theorem 2 as a
"warm-up" for Theorem 4.
4.2 Testability of the Dyck languages
It would be extremely nice to determine exactly which context-free languages are testable. At present
we seem to be very far from fullling this task. However, we are able to solve this question completely
for one family of context-free languages { the so called Dyck languages.
For an integer n  1, the Dyck language of order n, denoted by D n , is the language over the alphabet
of 2n symbols grouped into n ordered pairs (a The language D n
is dened by the following productions:
2.
3.
where
denotes the empty word. Though the words of D n are not binary according to the above
denition, we can easily encode them and the grammar describing them using only 0's and 1's. Thus we
may still assume that we are in the framework of languages over the binary alphabet. We can interpret
D n as the language with n distinct pairs of brackets, where a word w belongs to D n i it forms a
balanced bracket expression. The most basic and well known language in this family is D 1 , where we
have only one pair of brackets. Dyck languages play an important role in the theory of context-free
languages (see, e.g., [4] for a relevant discussion) and therefore the task of exploring their testability is
interesting.
Our rst goal in this subsection is to show that the language D 1 is testable. Let us introduce a
suitable notation. First, for the sake of simplicity we denote the brackets a
Assume that n is a large enough even number (obviously, for odd n we have D 1 \ f0; 1g
there is nothing to test in this case). Let w be a binary word of length n. For 1  i  n, we denote by
x(w; i) the number of 0's in the rst i positions of w. Also, y(w; i) stands for the number of 1 0 s in the
rst i positions of w. We have the following claims.
4.3 The word w belongs to D 1 if and only if the following two conditions hold: (a) x(w; i)
Proof. Follows easily from the denition of D 1 , for example, by induction on the length of w. We omit
a detailed proof. 2
Proof. Observe rst that by Claim 4.3 a word w is in D 1 if and only if we can partition its letters
into pairwise disjoint pairs, so that the left letter in each pair is a zero, and the right letter is a one.
Consider the bipartite graph, whose two classes of vertices are the set of indices i for which
and the set of indices i for which respectively, where each i with connected to all
assumption (a) and the defect form of Hall's theorem, this graph
contains a matching of size at least y(w; n) s 1 . By assumption (b), y(w; n)  n=2 s 2 =2. Therefore,
there are at least n=2 s 2 =2 s 1 disjoint pairs of letters in w, where in each pair there is a zero on
the left and a one on the right. Let us pair the remaining elements of w arbitrarily, where all pairs
but at most one consist of either two 0's or two 1's. By changing, now, when needed, the left entry of
each such pair to 0 and its right entry to 1 we obtain a word in D 1 , and the total number of changes
performed is at most (s 2 completing the proof. 2
a) If for some 1  i  n one has y(w; i) x(w; i)  s, then dist(w; D 1 )  s=2; b) If
Proof. Follows immediately from Claim 4.3. 2
We conclude from the above three claims that a word w is far from D 1 if and only if for some
coordinate i it deviates signicantly from the necessary and su-cient conditions provided by Claim 4.4.
This observation is used in the analysis of an algorithm for testing D 1 , proposed below.
where C > 0 is a su-ciently large constant, whose value will be chosen later, and assume d is an even
integer. In what follows we omit all
oor and ceiling signs, to simplify the presentation.
ALGORITHM
Input: a word w of length
1. Choose a sample S of bits in the following way: For each bit of w, independently and with
probability choose it to be in S. Then, if S contains more then d
'YES' without querying any bit. Else,
2. If dist(S; D 1 \ f0; 1g d 0
Lemma 4.6 The above algorithm outputs a correct answer with probability at least 2=3.
Proof. As we have already mentioned, we set
The proof contains two independent parts, in the rst we prove that the algorithm is correct (with
probability and in the second part we prove that the algorithm has a bounded error
for words w for which dist(w; D 1 )  n.
Consider rst the positive case w 2 D 1 . Set assume for simplicity that t as well as n=t
are integers. For 1  j  t, let X j be the number of 0's in S, sampled from the interval [1; nj=t]. Let
also Y j denote the number of 1's in S, sampled from the same interval. Both X j and Y j are binomial
random variables with parameters x(w; nj=t) and p, and y(w; nj=t) and p, respectively. As w 2 D 1 , we
get by Claim 4.3 that x(w; nj=t)  y(w; nj=t), implying EX j  EY j . Applying standard bounds on
the tails of binomial distribution, we obtain:
For . Note that EZ j  np=t. Using similar argumentation as above,
we get
As w 2 D 1 , we have by Claim 4.3 x(w; Hence
Finally, we have the following estimate on the distribution of the sample size jSj:
Choosing C large enough and recalling the denition of t, we derive from (1){(4) that with probability
at least 2=3 the following events hold simultaneously:
1.
2.
3. X t  np
4. jSj  np
Assume that the above four conditions are satised. Then we claim that dist(S; D 1 ) < . Indeed,
the rst two conditions guarantee that for all 1  i  jSj we have y(S; i) x(S; i)  =2+2np=t  2=3.
The last two conditions provide x(S; jSj) y(S; Therefore, by Claim
4.4 our algorithm will accept w with probability at least 2=3, as
required. This ends the rst part of the proof.
Let us now consider the negative case. Assume that dist(w; D 1 \ f0; 1g n )  n. By Claim 4.4 we
have then that at least one of the following two conditions holds: a) there exists an index 1  i  n, for
which y(w; i) x(w; i)  n=2; b) x(w; n) y(w; n)  n=2. In the former case, let X , Y be the number
of 0's, 1's, respectively, of S, sampled from the interval [1; i]. Let also k be the number of elements
from [1; i] chosen to S. Then are binomially distributed
with parameters x(w; i) and p, and y(w; i) and p, respectively. It follows from the denition of i that
EY EX  np=2. But then we have
Choosing the constant C to be su-ciently large and recalling the denitions of p and , we see that
the above probability is at most 1=6. But if y(S; it follows from Claim 4.5 that
If x(w; n) y(w; n)  n=2, we obtain, using similar arguments:
The above probability can be made at most 1=6 by the choice of C. But if x(S; jSj) y(S; jSj)  2, it
follows from Claim 4.5 that dist(S; D 1 )  . Thus in both cases we obtain that our algorithm accepts
w with probability at most 1=6. In addition, the algorithm may accept w (in each of the cases), when
(rst item in the algorithm). However, by equation (4) this may be bounded by 1/6
(choosing C as in the rst part). Hence the algorithm rejects w with probability at least 2=3. This
completes the proof of Lemma 4.6. 2.
By Lemma 4.6 we have the following result about the testability of the Dyck language D 1 .
Theorem 3 For every integer n and every small enough  > 0, there exists an -testing algorithm for
query complexity is C log(1=)= 2 for some absolute constant C > 0.
The reader has possibly noticed one signicant dierence between the algorithm of Section 2 for
testing regular languages and our algorithm for testing D 1 . While the algorithm for testing regular
languages has a one-sided error, the algorithm of this section has a two-sided error. This is not a
coincidence. We can show that there is no one-sided error algorithm for testing membership in D 1 ,
whose number of queries is bounded by a function of  only. Indeed, assume that A is a one-sided error
algorithm for testing D 1 . Consider its execution on the input word . It is easy to see
that dist(u; D 1 )  n. Therefore, A must reject u with probability at least 2=3. Fix any sequence of
coin tosses which makes A reject u and denote by Q the corresponding set of queried bits of u. We claim
that if jQ\[1; n=2+n]j  n=2 n, then there exists a word w of length n from D 1 , for which
for all i 2 Q. To prove this claim, we may clearly assume that jQ \ [1; n=2
as follows. For we take the rst n indices i in [1; n=2
and set For the last n indices i in [1; n=2
the su-cient condition for the membership in D 1 , given by Claim 4.3. Indeed,
at any point j in [1; n=2+ n] the number of 0's in the rst j bits of w is at least as large as the number
of 1's. Also, for j  n=2
Therefore w 2 D 1 . As A is assumed to be a one-sided error algorithm, it should always accept every
But then we must have jQ \ [1; n=2 queries a linear in n
number of bits. We have proven the following statement.
Proposition 3 Any one-sided error -test for membership in D 1
queries
n) bits on words of length
n.
Our next goal is to prove that all other Dyck languages, namely D k for all k  2 are non-testable.
We will present a detailed proof of this statement only for 2, but this clearly implies the result for
all k  3.
For the sake of clarity of exposition we replace the symbols a in the denition of D 2 by
respectively. Then D 2 is dened by the following context-free
where
is the empty word. Having in mind the above mentioned bracket interpretation of the Dyck
languages, we will sometimes refer to 0; 2 as left brackets and to 1; 3 as right brackets. Note that we
do not use an encoding of D 2 as a language over f0; 1g, but rather over an alphabet of size 4. Clearly,
non-testability of D 2 as dened above will imply non-testability of any binary encoding of D 2 that is
obtained by a xed binary encoding of f0; 1; 2; 3g.
Theorem 4 The language D 2 is not -testable.
Proof. Let n be a large enough integer, divisible by 8. We denote L Using Yao's
principle, we assign a probability distribution on inputs of length n and show that any deterministic
algorithm probing bits outputs an incorrect answer with probability 0:5  o(1). Both positive
and negative words will be composed of three parts: The rst which is a sequence of matching 0=1
(brackets of the rst kind) followed by a sequence of 0=2 (left brackets) and a sequence of 1=3 (right
brackets).
Positive instances are generated according to the distribution P as follows: choose k uniformly at
random in the range Given k, the word of length n is is of length n 2k
generated by: for choose v[i] at random from 0; 2 and then set v[n 2k+1
Negative instances are chosen as follows: the process is very similar to the positive case except that
we do not have the restriction on v[n 2k 1. Namely, we choose k at random in the
range Given k, a word of length n is is of length n 2k generated by:
choose v[i] at random from 0; 2 and for choose v[n 2k +1 i]
at random from 1; 3. Let us denote by N the distribution at this stage. Note that the words that are
generated may be of distance less than n from L n (in fact some words in L n are generated too). Hence
we further condition N on the event that the word is of distance at least n from L n .
The probability distribution over all inputs of length n is is now dened by choosing with probability
1/2 a positive instance, generated as above, and with probability 1/2 a negative instance, chosen
according to the above described process.
4.7 The probability that an instance generated according to N is n-close to some word in L n
is exponentially small in n.
Proof. Fix k and let be a word of length n generated by N . For such xed k the three parts
of w are the rst part of matching 0=1 of length 2k, the second part which is a random sequence of 0=2
of length n 2kand the third part which is a random sequence of 1=3 of length n 2k. Let us denote by
these three disjoint sets of indices of w.
We will bound from above the number of words w of length n of the form
2kwhich are at distance at most n from L n . First we choose the value of w on N 2 , which gives 2 n 2kpossibilities. Then we choose (at most) n bits of w to be changed to get a word from L n ( n
choices)
and set those bits (4 n possibilities). At this point, the only part of w still to be set is its value of N 3 ,
where we are allowed to use only right brackets 1; 3. The word to be obtained should belong to L n . It
is easy to see that there is at most one way to complete the current word to a word in L n using right
brackets only. Hence the number of such words altogether is at most 2 n 2k
. The total number
of words w of the form 0
and each such word gets the same probability
in the distribution N . Therefore the probability that a word chosen according to N is n-close to L n
can be estimated from above by
n=4
))n+2n n
for small enough  > 0 as promised. 2
d, be a xed set of places and let k be chosen uniformly at random in the
range n=8; :::; n=4. Then S contains a pair i < j symmetric with respect to (n 2k)=2 with probability
at most d 8
n .
Proof. For each distinct pair there is a unique k for which are symmetric with respect to
the above point. Hence the above probability is bounded by d 8
We now return to the proof of Theorem 4. Let A be an algorithm for testing L n that queries at
most queries. As may assume that A is non-adaptive, namely, it queries some
xed set of places S of size d (as every adaptive A can be made non adaptive by querying ahead at
most 2 d possible queries dened by two possible branchings after each adaptive query. We then look at
these queries as our S). For any possible set of answers f and an input
the event that w is consistent with f on S. Let NoSym be the event that S contains
no symmetric pair with respect to (n 2k)=2. Also, let F 0 denote all these f 's on which the algorithm
answers 'NO' and let F 1 be all these f 's on which it answers 'YES'. Finally denote by (w positive) and
(w negative) the events that a random w is a positive instance and a negative instance, respectively.
The total error of the algorithm is
However, given that S contains no symmetric pairs, for a xed f , Prob[f w ^ (w is negative)] is
essentially equal to Prob[f w ^ (w is positive)] (these probabilities would be exactly equal if negative
w would be generated according to N . Claim 4.7 asserts that N is exponentially close to the real
distribution on negative instances). Hence each is of these probabilities is 0:5Prob[f w jNoSym]  o(1).
Plugging this into the sum above, and using Claim 4.8 we get that the error probability is bounded
from below by Prob(NoSym)
f (0:5  o(1))Prob[f w jNoSym]  (1 d 8
Concluding remarks
The main technical achievement of this paper is a proof of testability of regular languages. A possible
continuation of the research is to describe other classes of testable languages and to formulate su-cient
conditions for a context-free language to be testable (recall that in Theorem 2 we have shown that not
all context-free languages are testable).
One of the most natural ways to describe large classes of testable combinatorial properties is by
putting some restrictions on the logical formulas that dene them. In particular we can restrict the arity
of the participating relations, the number of quantier alternations, the order of the logical expression
(rst order, second order), etc.
The result of the present paper is an example to this approach, since regular languages are exactly
those that can be expressed in second order monadic logic with a unary predicate and an embedded
linear order. Another example can be found in a sequel of this paper [1], which addresses testability of
graph properties dened by sentences in rst order logic with binary predicates, and which complements
the class of graph properties shown to be testable by Goldreich et al [7]. Analogous results for predicates
of higher arities would be desirable to obtain, but technical di-culties arise when the arity is greater
than two.
As a long term goal we propose a systematic study of the testability of logically dened classes.
Since many dierent types of logical frameworks are known, to nd out which one is suited for this
study is a challenge. Virtually all single problems that have been looked at so far have the perspective
of being captured by a more general logically dened class with members that have the same testability
properties.
A very dierent avenue is to try to develop general combinatorial techniques for proving lower
bounds for the query complexity of testing arbitrary properties, possibly by nding analogs to the block
sensitivity [12] and the Fourier analysis [11] approaches for decision tree complexity. At present we have
no candidates for combinatorial conditions that would be both necessary and su-cient for -testability.

Acknowledgment

. We would like to thank Oded Goldreich for helpful comments. We are also grateful
to the anonymous referees for their careful reading.



--R


Proof veri


Proof of a conjecture by Erd

Property testing and its connections to learning and approximation.
Introduction to Automata Theory
A bound for a solution of a linear Diophantine problem
New directions in testing
On the degree of Boolean functions as real polynomials

Robust characterization of polynomials with applications to program testing.
Probabilistic computation
--TR

--CTR
Michal Parnas , Dana Ron , Ronitt Rubinfeld, Testing membership in parenthesis languages, Random Structures & Algorithms, v.22 n.1, p.98-138, January
Beate Bollig, A large lower bound on the query complexity of a simple boolean function, Information Processing Letters, v.95 n.4, p.423-428, 31 August 2005
Beate Bollig , Ingo Wegener, Functions that have read-once branching programs of quadratic size are not necessarily testable, Information Processing Letters, v.87 n.1, p.25-29, July
Eldar Fischer, On the strength of comparisons in property testing, Information and Computation, v.189 n.1, p.107-116, 25 February 2004
Eldar Fischer , Eric Lehman , Ilan Newman , Sofya Raskhodnikova , Ronitt Rubinfeld , Alex Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Eli Ben-Sasson , Prahladh Harsha , Sofya Raskhodnikova, Some 3CNF properties are hard to test, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Alon, Testing subgraphs in large graphs, Random Structures & Algorithms, v.21 n.3-4, p.359-370, October 2002
Eldar Fischer , Ilan Newman , Ji Sgall, Functions that have read-twice constant width branching programs are not necessarily testable, Random Structures & Algorithms, v.24 n.2, p.175-193, March 2004
Alon , Asaf Shapira, Every monotone graph property is testable, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Asaf Shapira, A combinatorial characterization of the testable graph properties: it's all about regularity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Alon , Asaf Shapira, Testing subgraphs in directed graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Alon , Asaf Shapira, A characterization of easily testable induced subgraphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
regular languages;context-free languages;property testing