Testable and untestable classes of first-order logic
Charles Harold Jordan · 2012
Property testing is essentially a kind of constant-time randomized approxima-tion. Alon et al. [3] were the first to consider the idea of testing properties ex-pressible in syntactic subclasses of first-order logic. They proved the testability of all properties of undirected, loop-free graphs expressible with quantifier prefix 98, and also that there exist untestable properties of undirected, loop-free graphs expressible with quantifier prefix 89. In this dissertation, we continue the study of testing subclasses of first-order logic. In particular, we focus on the classification of prefix-vocabulary classes, or classes defined by quantifier prefix and vocabulary, according to their testability. The main results are as follows. First, we develop a framework for relational property testing including variations corresponding to the different models con-sidered in the literature for non-uniform hypergraph testing. We then use this framework to prove the following. 1. All (relational) properties expressible by formulae in Ackermann’s class with