Testable and untestable classes of first-order formulae

DOI 機関リポジトリ (HANDLE) HANDLE Web Site Web Site 参考文献44件 オープンアクセス

この論文をさがす

説明

In property testing, the goal is to distinguish structures that have some desired property from those that are far from having the property, based on only a small, random sample of the structure. We focus on the classification of first-order sentences according to their testability. This classification was initiated by Alon et al. [2], who showed that graph properties expressible with prefix there exists*for all* are testable but that there is an untestable graph property expressible with quantifier prefix for all*there exists*. The main results of the present paper are as follows. We prove that all (relational) properties expressible with quantifier prefix there exists*for all there exists* (Ackermann's class with equality) are testable and also extend the positive result of Alon et al. [2] to relational structures using a recent result by Austin and Tao [8]. Finally, we simplify the untestable property of Alon et al. [2] and show that prefixes for all(3)there exists, for all(2)there exists for all, for all there exists for all(2) and for all there exists V there exists can express untestable graph properties when equality is allowed.

収録刊行物

参考文献 (44)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ