A-022 Relational Properties Expressible with One Universal Quantifier are Testable (Extended Abstract)

概要

論文の詳細を見る
Property testing is an application of induction in which we take a small, random sample of an object and wish 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. Although much of the recent work has focused on graphs, we outline some of our recent work on testing properties of relational structures. We introduce three generalized models for relational testing and use these models to consider the logical classification problem for testability, where we state one of our recent results : Ackermann's class with equality is testable.
FIT(電子情報通信学会・情報処理学会)推進委員会の論文
2009-08-20