| Presentation | 1995/9/20 On the Power of Self-Testers and Self-Correctors Hiroyoshi Mori, Toshiya Itoh, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A checker, a self-tester, and a self-corrector for a function f are known as powerful tools in designing programs that compute f, however, the relationships among them have not been known well. In this paper, we show first that (1) if oneway permutations exist, then there exists a language L that has a checker but does not have a self-corrector. We then introduce a novel notion of "self-improvers" that transform a faulty program into a less faulty program, and show that (2) if a function f has self-tester/corrector pair, then f has a self-improver. As the applications of self-improvers, we finally show that (3) if a function f has a self-tester/corrector pair, then f has a flexible self-tester and (4) if a function f has a self-tester/corrector pair, then f has a self-improver that transforms a faulty program into an almost correct program. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Program Checkers / Self-Testers / Self-Correctors / Self-Tester/Corrector Pairs |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 1995/9/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Power of Self-Testers and Self-Correctors |
| Sub Title (in English) | |
| Keyword(1) | Program Checkers |
| Keyword(2) | Self-Testers |
| Keyword(3) | Self-Correctors |
| Keyword(4) | Self-Tester/Corrector Pairs |
| 1st Author's Name | Hiroyoshi Mori |
| 1st Author's Affiliation | Department of Information Processing, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology() |
| 2nd Author's Name | Toshiya Itoh |
| 2nd Author's Affiliation | Department of Information Processing, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology |
| Date | 1995/9/20 |
| Paper # | |
| Volume (vol) | vol.95 |
| Number (no) | 240 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |