Untestable Properties in the Kahr-Moore-Wang Class

Authors: Charles Jordan1 and Thomas Zeugmann2

Source: Logic, Language, Information and Computation,
18th International Workshop, WoLLIC 2011, Philadelphia, PA, USA, May 18-21, 2011, Proceedings
, (Lev D. Beklemishev and Ruy De Queiroz, Eds.),
Lecture Notes in Artificial Intelligence 6642, pp. 176-186, Springer 2011.

Abstract. Property testing is a kind of randomized approximation in which one takes a small, random sample of a structure and wishes to determine whether the structure satisfies some property or is far from satisfying the property. We focus on the testability of classes of first-order expressible properties, and in particular, on the classification of prefix-vocabulary classes for testability. The main result is the untestability of [∀∃∀,(0,1)]=. This is a well-known class and minimal for untestability. We discuss what is currently known about the classification for testability and briefly compare it to other classifications.

Keywords: property testing, logic, randomized algorithms.

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

Valid HTML 4.1