Relational Properties Expressible with One Universal Quantifier are Testable
Authors: Charles Jordan1 and Thomas Zeugmann2
Source: Stochastic Algorithms: Foundations and Applications, 5th International Symposium, SAGA 2009, Sapporo, Japan, October 2009, Proceedings , (Osamu Watanabe and Thomas Zeugmann, Eds.), Lecture Notes in Computer Science 5792, pp. 141-155, Springer 2009.
Abstract. In property testing a small, random sample of an object is taken and one wishes to distinguish with high probability between the case where it has a desired property and the case where it is far from having the property. Much of the recent work has focused on graphs. In the present paper three generalized models for testing relational structures are introduced and relationships between these variations are shown.
Furthermore, the logical classification problem for testability is considered and, as the main result, it is shown that Ackermann's class with equality is testable.
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 2009, Springer
