کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430292 | 687959 | 2012 | 22 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Testable and untestable classes of first-order formulae Testable and untestable classes of first-order formulae](/preview/png/430292.png)
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. (2000) [2], who showed that graph properties expressible with prefix ∃⁎∀⁎∃⁎∀⁎ are testable but that there is an untestable graph property expressible with quantifier prefix ∀⁎∃⁎∀⁎∃⁎. The main results of the present paper are as follows. We prove that all (relational) properties expressible with quantifier prefix ∃⁎∀∃⁎∃⁎∀∃⁎ (Ackermannʼs class with equality) are testable and also extend the positive result of Alon et al. (2000) [2] to relational structures using a recent result by Austin and Tao (2010) [8]. Finally, we simplify the untestable property of Alon et al. (2000) [2] and show that prefixes ∀3∃∀3∃, ∀2∃∀∀2∃∀, ∀∃∀2∀∃∀2 and ∀∃∀∃∀∃∀∃ can express untestable graph properties when equality is allowed.
► We deal with the logical classification of testability.
► We examine the testability of prefix-vocabulary classes of first-order logic.
► We prove that Ackermannʼs class with equality is testable with one-sided error.
► We show that Ramseyʼs class is testable.
► We show that there are untestable properties expressible with four quantifiers.
Journal: Journal of Computer and System Sciences - Volume 78, Issue 5, September 2012, Pages 1557–1578