| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 5A |
| セッション名 |
| 情報検索・論理・オートマトン |
| 講演日 |
| 2009/09/03 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| A-022 |
| タイトル |
| Relational Properties Expressible with One Universal Quantifier are Testable (Extended Abstract) |
| 著者名 |
| Jordan Charles, Zeugmann Thomas, |
| キーワード |
| property testing, logic, Ackermann's class |
| 抄録 |
| 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 prove our main result: Ackermann's class with equality is testable. |
| 本文pdf |
| PDF download (159.5KB) |