Testable and untestable classes of first-order formulae

Authors: Charles Jordan¹ and Thomas Zeugmann²

Source: Journal of Computer and System Sciences Vol. 78, No. 5, 2012, 1557 - 1578.

Abstract. In property testing, the goal is to distinguish structures that have some desired property from those that are far from having the property, based on only a small, random sample of the structure. We focus on the classification of first-order sentences according to their testability. This classification was initiated by Alon et al. (2000), who showed that graph properties expressible with prefix ∃^*∀^* are testable but that there is an untestable graph property expressible with quantifier prefix ∀^*∃^*. The main results of the present paper are as follows. We prove that all (relational) properties expressible with quantifier prefix ∃^*∀∃^* (Ackermann's class with equality) are testable and also extend the positive result of Alon et al. (2000) to relational structures using a recent result by Austin and Tao (2010). Finally, we simplify the untestable property of Alon et al. (2000) and show that prefixes ∀³∃, ∀²∃∀, ∀∃∀² and ∀∃∀∃ can express untestable graph properties when equality is allowed.

Keywords: Property testing; Logic; Randomized algorithms; Ackermann's class; Ramsey's class