The Kahr-Moore-Wang Class Contains Untestable Properties

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,...

Full description

Saved in:
Bibliographic Details
Published in:Baltic Journal of Modern Computing 2016-01, Vol.4 (4), p.736-736
Main Authors: Jordan, Charles, Zeugmann, Thomas
Format: Article
Language:English
Subjects:
Approximation
Classification
Computation
Mathematical analysis
Testability
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2255-8950
2255-8942
2255-8950
DOI:10.22364/bjmc.2016.4.4.11