Date: Fri Nov 27 21:37:53 2009

Title: Contributions to the Classification for Testability: Four Universal and One Existential Quantifier

Authors: Charles Jordan and Thomas Zeugmann


  • First name: Charles
  • Last name: Jordan
  • Address: Division of Computer Science, Hokkaido University, North 14, West 9, Sapporo 060-0814, Japan
  • Email:

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 begun 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 ∀*∃*. We simplify their untestable example and therefore show that there is an untestable graph property expressible with each of the following quantifier patterns: ∀⁴∃, ∀³∃∀, ∀²∃∀² and ∀∃∀³.

©Copyright 2009 Authors