Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments
View/ Open
Issue Date
1996Author
Romanik, Kathleen
Vitter, Jeffrey Scott
Publisher
Elsevier
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
We examine the complexity of testing di erent program constructs. We do this
by de ning a measure of testing complexity known as VCP-dimension, which is similar to the
Vapnik-Chervonenkis dimension, and applying it to classes of programs, where all programs
in a class share the same syntactic structure. VCP-dimension gives bounds on the number
of test points needed to determine that a program is approximately correct, so by studying
it for a class of programs we gain insight into the di culty of testing the program construct
represented by the class. We investigate the VCP-dimension of straight line code, if-then-
else statements, and for loops. We also compare the VCP-dimension of nested and sequential
if-then-else statements as well as that of two types of for loops with embedded if-then-else
statements. Finally, we perform an empirical study to estimate the expected complexity of
straight line code.
Collections
Citation
K. Romanik and J. S. Vitter. “Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments,” Information and Computation, 128(2), August 1, 1996, 87–108. An extended abstract appears in “Using Computational Learning Theory to Analyze the Testing Complexity of Program Segments,” Proceedings of the 17th Annual IEEE International Computer Software and Applications Conference (COMPSAC ’93), Phoenix, AZ, 1993, 367–373. http://dx.doi.org/10.1006/inco.1996.0065
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.