The problem of determining whether two programs compute the same function is undecidable. We restrict the class of functions that a program can compute to be a finite dimensional vector space, enabling the problem to become tractable. We prove a theorem showing that the number of test points needed to distinguish any such programs is equal to the dimension of the vector space of functions which they compute, thus generalizing previous results of Howden. Our result unifies certain existing software testing theory and explains the successes and failures of one existing method for selecting test data called perturbation testing. We apply the theorem to obtain three results on the number of test points required to test in vector spaces of Boolean functions and polynomials. First, the Vandermonde matrix used together with our theorem yields the classical result that a polynomial of degree at most n is determined by n+1 points. Second, in vector spaces of Boolean functions we obtain useful results when the degree of the Boolean function is less than the number of inputs to the function. Third, we apply our theorem to describe a technique for testing nonpolynomial, real valued functions.

Article How to break Gifford's cipher (extended abstract) Share on Authors: Thomas R. Cain Computer Science Department, University of Maryland Baltimore County, Baltimore, Maryland Computer Science Department, University of Maryland Baltimore County, Baltimore, MarylandView Profile , Alan T. Sherman Computer Science Department, University of Maryland Baltimore County, Baltimore, Maryland Computer Science Department, University of Maryland Baltimore County, Baltimore, MarylandView Profile Authors Info & Claims CCS '94: Proceedings of the 2nd ACM Conference on Computer and communications securityNovember 1994 Pages 198–209https://doi.org/10.1145/191177.191227Online:02 November 1994Publication History 3citation540DownloadsMetricsTotal Citations3Total Downloads540Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access