Untestable Properties Expressible with Four First-Order Quantifiers

Authors: Charles Jordan1 and Thomas Zeugmann2

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: ∀∃∀∃, ∀∃∀2, ∀2∃∀ and ∀3∃.

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 2010, Springer

Valid HTML 4.1