Testable and untestable classes of first-order formulae

Authors: Charles Jordan1 and Thomas Zeugmann2

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 ∀3∃, ∀2∃∀, ∀∃∀2 and ∀∃∀∃ can express untestable graph properties when equality is allowed.

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

1 Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
2 Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas under Grant No. 21013001.
©Copyright 2012, Elsevier Inc.
Valid HTML 4.1