학술논문

On the selection of test data for recursive mathematical subroutines.
Document Type
Journal
Author
Rowland, John H. AMS Author Profile; Davis, Philip J. AMS Author Profile
Source
SIAM Journal on Computing (SIAM J. Comput.) (19810101), 10, no. 1, 59-72. ISSN: 0097-5397 (print).
Subject
39 Difference and functional equations -- 39A Difference equations
  39A10 Difference equations, additive

68 Computer science -- 68B Software
  68B10 Analysis of programs
Language
English
ISSN
00975397
Abstract
Authors' summary: ``Let $Y$ be a family of sequences defined by lineardifference equations of the form $y(n+1)=P(n)y(n)+Q(n)$, where $P$ and $Q$are restricted to be polynomials of limited degree, constant matrices,multinomials, and so forth. The central problem is to find a finite samplewhich uniquely identifies members of $Y$. It is shown that such a sampleexists when $P$ and $Q$ are polynomials of limited degree. The sample sizedepends linearly on the degree limits. A similar result holds for systemsof difference equations with $P$ a constant matrix and $Q$ a column vectorwith polynomial components. Testingprocedures are also derived for the case where the coefficients of $P$ and$Q$ are multinomials in a vector parameter $x$, and $y$ is considered to bea function of its initial value.''