The Kahr–Moore–Wang Class Contains Untestable Properties

Authors: Charles Jordan* and Thomas Zeugmann**

Source: Baltic Journal of Modern Computing Vol. 4, Number 4, 2016, 736–752.

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)]=. We also show that this class remains untestable without equality in at least one model of testing. These classes are well-known and (at least one is) 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, Kahr–Moore–Wang class

* Supported by JSPS Grant Nos. 15H00847, ‘Exploring the Limits of Computation’ (ELC), and 16H02785.
** Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas under Grant No. 21013001.
©Copyright 2016, Authors
Valid HTML 4.1