On the Power of Self-Testers and Self-Correctors

Hiroyoshi MORI; Toshiya ITOH

On the Power of Self-Testers and Self-Correctors

Hiroyoshi MORI, Toshiya ITOH

Full Text Views

0

Cite this

Summary :

Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show 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 trans form a faulty program into a less faulty program, and show that (2) if a function f has a 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 self-improver that transforms a faulty program into an alomost correct program.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.1 pp.98-106

Publication Date: 1997/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Cite this

Copy

Hiroyoshi MORI, Toshiya ITOH, "On the Power of Self-Testers and Self-Correctors" in IEICE TRANSACTIONS on Fundamentals, vol. E80-A, no. 1, pp. 98-106, January 1997, doi: .
Abstract: Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show 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 trans form a faulty program into a less faulty program, and show that (2) if a function f has a 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 self-improver that transforms a faulty program into an alomost correct program.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_1_98/_p

Copy

@ARTICLE{e80-a_1_98,
author={Hiroyoshi MORI, Toshiya ITOH, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Power of Self-Testers and Self-Correctors},
year={1997},
volume={E80-A},
number={1},
pages={98-106},
abstract={Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show 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 trans form a faulty program into a less faulty program, and show that (2) if a function f has a 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 self-improver that transforms a faulty program into an alomost correct program.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - On the Power of Self-Testers and Self-Correctors
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 98
EP - 106
AU - Hiroyoshi MORI
AU - Toshiya ITOH
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1997
AB - Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show 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 trans form a faulty program into a less faulty program, and show that (2) if a function f has a 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 self-improver that transforms a faulty program into an alomost correct program.
ER -