Recent Progress in the Classification for Testability
Charles Jordan∗ and Thomas Zeugmann†
Department of Information Science and Technology
Hokkaido University, Sapporo 060-0814, Japan∗ Tel/Fax: +81-11-706-7675, Email: skip@ist.hokudai.ac.jp† Tel/Fax: +81-11-706-7684, Email: thomas@ist.hokudai.ac.jp

Abstract—In property testing we wish to distinguish between
objects that have a given property and objects that are far fromhaving the property, after examining only a small portion ofthe object. The classification problem for testability focuses onproperties that are expressible in sentences of first-order logic,
and asks us to determine which prefix vocabulary classes of firstorder logic are testable and which are not.
Here we review recent results concerning this classification.

I. I NTRODUCTION
In property testing, we take a small, random sample of alarge structure and wish to determine if the structure has somedesired property or if it is far from having the property. The
hope is that we can gain efficiency in return for not deciding
the problem exactly. We are particularly interested in firstorder expressible properties and seek to obtain a complete
classification of the testable and untestable prefix vocabularyclasses of first-order logic. Here we introduce some of ourrecent results concerning this classification; proofs of all
theorems can be found in the references.
The paper is structured as follows. In Section II we briefly
outline the history of property testing, focusing particularly on
previous work concerning the classification for testability. We
give definitions and notation in Section III. In Section IV we
describe some recent results in the classification for testability.
II. BACKGROUND
The study of property testing began in formal verification(see the recent introduction to graph property testing by
Goldreich [1] and the recent surveys by Ron [2], [3] forreferences and additional background), and attention soon
focused on testing graph and string properties. Alon et al. [4]showed that the regular languages are testable, implying thetestability of monadic first-order logic1 .
Alon et al. [6] began a logical characterization of thetestable (graph) properties. They showed that all graph properties expressible in first-order formulas with quantifier pattern“∃∗ ∀∗ ” (Ramsey’s class) are testable, and that there exist
untestable graph properties expressible with quantifier pattern“∀∗ ∃∗ ”. The example they give is expressible with 17 variables
and prefix ∀12 ∃5 . See Section IV for more recent results
concerning the logical classification for testability.
The first author is supported by a Grant-in-Aid for JSPS Fellows underGrant No. 2100195209. The second author is supported by MEXT Grant-inAid for Scientific Research on Priority Areas under Grant No. 21013001.
1 Recall that monadic first-order logic characterizes a subclass of the regularlanguages (cf. McNaughton and Papert [5]).

Although much of the research in property testing has
focused on graph properties (see Alon and Shapira [7] fora survey), very recently there has been a significant effort
to generalize these results in a variety of ways, usually
via applications of generalizations of Szemerédi’s Regularity
Lemma. In particular, Austin and Tao [8] have recently shownthat all hereditary properties of colored, directed hypergraphs
are testable, generalizing a series of related results. We omit
more detailed citations due to space constraints.
III. P RELIMINARIESWe are interested in properties expressible in first-orderlogic, and so we begin with logical definitions. We restrict
ourselves to very brief, informal definitions due to spaceconstraints; see Jordan and Zeugmann [9] for details.
Definition 1. A vocabulary τ is a tuple of distinct predicate
symbols Ri together with their arities ai ,
τ := (R1a1 , . . . , Rsas ) .
For example, the vocabulary of directed graphs isτG := (E 2 ).
Definition 2. A structure A of type τ is an (s + 1)-tuple
AA := (U, RA
1 , . . . , Rs ) ,ai
where U is a finite universe and each RA
is a predicatei ⊆Ucorresponding to the predicate symbol Ri of τ .

A property of type τ is any set of structures of type τ . In
property testing, our goal is to distinguish between structuresthat have a property and those which are far from having theproperty. This requires a distance measure, for example we
could say that a structure is ε-far from a property P if wemust modify more than an ε-fraction of its representation toobtain a structure with P . See Jordan and Zeugmann [9] fora discussion of alternative distances.
Definition 3. A property P is testable if, for every ε > 0,
there exist randomized approximation algorithms satisfying thefollowing. After examining at most c(ε) bits of a structure
A, the algorithm accepts with probability 2/3 if A ∈ P andrejects with probability 2/3 if A is ε-far from P .
Definition 3 is non-uniform in that we allow different
algorithms for each choice of ε and so it is natural to consider

uniformity conditions. There exist properties that are nonuniformly testable but not uniformly testable, however ourresults hold in both the uniform and non-uniform cases andso we will no longer distinguish between the two.
Finally, we briefly outline the relevant definitions for classification, see Börger et al. [10] for more formal definitions andhistory. A prefix vocabulary class is a triple [Π, p]e , where Π isa string over the alphabet {∃, ∀, ∃∗ , ∀∗ }, p is either a sequence
over the naturals and first infinite ordinal or the phrase “all”,and e is either ’=’ or the empty string.

graphs and so it is natural to consider other types of structures. We generalized the concept of testability to relational
structures and showed the following.

Definition 4. First-order formula ϕ := π1 x1 π2 x2 . . . πr xr : ψin prenex normal form, with quantifiers πi and quantifier-free
ψ, belongs to the prefix vocabulary fragment defined by [Π, p]e
if the following conditions are satisfied.
1) The string π1 π2 . . . πr is contained in the language
specified by Π when Π is interpreted as a regularexpression.
2) If p is not all, at most pi distinct predicate symbols ofarity i appear in ψ.
3) Equality (=) appears in ψ only if e is ‘=’.

Theorem 4 (Jordan and Zeugmann [15]). All formulas in[∃∗ ∀∗ , all]= define properties that are testable.

The goal in the classification problem for testability is toobtain a complete classification of which prefix vocabularyclasses are testable and which are not.
IV. R ECENT R ESULTS
The classification of prefix vocabulary classes of firstorder logic was started by Alon et al. [6]. They showed thatundirected, loop-free properties expressible in [∃∗ ∀∗ , (0, 1)]=
are testable and that there exists an untestable property expressible in [∀12 ∃5 , (0, 1)]= . When studying the classification
problem, it is necessary to minimize the number of quantifiers
needed to express untestable properties. Additionally, the firstorder theory of graphs is not restricted to undirected, loopfree graphs. Accordingly, we have recently simplified theuntestable example from Alon et al. [6], giving the following.
Theorem 1 (Jordan and Zeugmann [11]). The following prefix
vocabulary classes are not testable:1) [∀3 ∃, (0, 1)]=2) [∀2 ∃∀, (0, 1)]=3) [∀∃∀2 , (0, 1)]=4) [∀∃∀∃, (0, 1)]=The specific example used is essentially an encoding in
directed graphs of undirected graph isomorphism2 . Very recently, we have used a somewhat more complicated property(related to Boolean function isomorphism) to sharpen three ofthese prefixes as follows.
Theorem 2 (Jordan and Zeugmann[13]). There are untestable√properties (even given o( n) queries) in [∀∃∀, (0, 1)]= .
The proof applies ideas from Alon and Blais [14]. However,first-order logic is not restricted to expressing properties of
2 Graph isomorphism is generally hard for testing, see, e.g., Fischer andMatsliah [12].

Theorem 3 (Jordan and Zeugmann [9]). All formulas in[∃∗ ∀∃∗ , all]= define properties that are testable.
This is Ackermann’s class with equality, which has many
nice properties. We have also applied a strong result by Austinand Tao [8] to extend the positive result of Alon et al. [6] fromundirected, loop-free graphs to relational structures.

This is (the full) Ramsey’s class, which also has many niceproperties. The current classification is consistent with theclassifications for the finite model property, docility and associated second-order 0-1 laws. We are particularly interested
in the testability of variants of the Gödel class (i.e., classescontaining [∀2 ∃, (0, 1)]). Determining whether these classes
are testable would complete the classification for the special
case of predicate logic with equality.
R EFERENCES[1] O. Goldreich, “Introduction to testing graph properties,” Electronic
Colloquium on Computational Complexity (ECCC), Tech. Rep. TR10082, May 2010.
[2] D. Ron, “Property testing: A learning theory perspective,” Found. Trends
Mach. Learn., vol. 1, no. 3, pp. 307–402, 2008.
[3] ——, “Algorithmic and analysis techniques in property testing,” Found.
Trends Theor. Comput. Sci., vol. 5, no. 2, pp. 73–205, 2009.
[4] N. Alon, M. Krivelevich, I. Newman, and M. Szegedy, “Regular languages are testable with a constant number of queries,” SIAM J. Comput.,vol. 30, no. 6, pp. 1842–1862, 2001.
[5] R. McNaughton and S. Papert, Counter-Free Automata. M.I.T. Press,1971.
[6] N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, “Efficient testingof large graphs,” Combinatorica, vol. 20, no. 4, pp. 451–476, 2000.
[7] N. Alon and A. Shapira, “Homomorphisms in graph property testing,”
in Topics in Discrete Mathematics, ser. Algorithms and Combinatorics,
M. Klazar, J. Kratochvı́l, M. Loebl, J. Matoušek, R. Thomas, and P. Valtr,Eds. Springer, 2006, vol. 26, pp. 281–313.
[8] T. Austin and T. Tao, “On the testability and repair of hereditary
hypergraph properties,” Random Struct. Algorithms, vol. 36, no. 4, pp.
373–463, 2010.
[9] C. Jordan and T. Zeugmann, “Relational properties expressible with one
universal quantifier are testable,” in Proc. SAGA 2009, ser. Lecture Notes
in Computer Science, O. Watanabe and T. Zeugmann, Eds., vol. 5792.
Springer, 2009, pp. 141–155.
[10] E. Börger, E. Grädel, and Y. Gurevich, The Classical Decision Problem.
Springer-Verlag, 1997.
[11] C. Jordan and T. Zeugmann, “Untestable properties expressible withfour first-order quantifiers,” in Proc. LATA 2010, ser. Lecture Notes inComputer Science, A.-H. Dediu, H. Fernau, and C. Martı́n-Vide, Eds.,
vol. 6031. Springer, 2010, pp. 333–343.
[12] E. Fischer and A. Matsliah, “Testing graph isomorphism,” SIAM J.
Comput., vol. 38, no. 1, pp. 207–225, 2008.
[13] C. Jordan and T. Zeugmann, “Untestable properties in the Kahr-MooreWang class,” in Proc. WoLLIC 2011, ser. Lecture Notes in Computer
Science, L. Beklemishev and R. de Queiroz, Eds., vol. 6642. Springer,
2011, pp. 176–186.
[14] N. Alon and E. Blais, “Testing Boolean function isomorphism,” in Proc.
RANDOM 2010, ser. Lecture Notes in Computer Science, vol. 6302.
Springer, 2010, pp. 394–405.
[15] C. Jordan and T. Zeugmann, “A note on the testability of Ramsey’sclass,” in Proc. TAMC 2010, ser. Lecture Notes in Computer Science,J. Kratochvı́l, A. Li, J. Fiala, and P. Kolman, Eds., vol. 6108. Springer,
2010, pp. 296–307.