Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments

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. A shortened version 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 (COMpostscriptAC '93), Phoenix, 1993, 367-373.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

We examine the complexity of testing different program constructs. We do this by defining 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 difficulty 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.