Testing nonlinear operators

We study testing of nonlinear operators; we want to test whether an implementation operator conforms to a specification operator. The problem is difficult, since there can be infinitely many possible inputs but we can only test finitely many of them. An implementation operator may perform well on the tested inputs but may be faulty on the untested inputs. In general, finite testing is inherently inconclusive. Consequently, we modify the problem in three different directions and obtain positive results: (1) We consider an infinite sequence of tests and prove that testing is decidable in the limit; (2) We relax the error criterion and show that finite testing is conclusive, however, the cost could be formidable; and (3) We tolerate faults on a negligible subset of inputs and develop a probabilistic testing algorithm with a significantly reduced cost. Our results indicate that test sets are universal; they only depend on the structure of the input set. In fact, they are provided by an net of the input set.This work was done while consulting at AT&T Bell Laboratories, and is partially supported by the National Science Foundation grant IRI-89-07215 and the Air Force Office of Scientific Research 91-0347.