학술논문

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
Abstract
Authors' summary: ``Let $Y$ be a family of sequences defined by linear difference 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 sample which uniquely identifies members of $Y$. It is shown that such a sample exists when $P$ and $Q$ are polynomials of limited degree. The sample size depends linearly on the degree limits. A similar result holds for systems of difference equations with $P$ a constant matrix and $Q$ a column vector with polynomial components. Testing procedures 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 be a function of its initial value.''