Untestable Properties Expressible with Four First-Order Quantifiers

Authors: Charles Jordan¹ and Thomas Zeugmann²

Source: Language and Automata Theory and Applications, 4th International Conference, LATA 2010, Trier, Germany, Mai 24-28, 2010, Proceedings , (Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide, Eds.), Lecture Notes in Computer Science 6031, pp. 333-343, Springer 2010.

Abstract. In property testing, the goal is to distinguish between structures that have some desired property and those that are far from having the property, after examining only a small, random sample of the structure. We focus on the classification of first-order sentences based on their quantifier prefixes and vocabulary into testable and untestable classes. This classification was initiated by Alon et al. [1], who showed that graph properties expressible with quantifier patterns ∃^*∀^* are testable but that there is an untestable graph property expressible with a quantifier pattern ∀^*∃^*. In the present paper, their untestable example is simplified. In particular, it is shown that there is an untestable graph property expressible with each of the following quantifier patterns: ∀∃∀∃, ∀∃∀², ∀²∃∀ and ∀³∃.