On the Small-Scope Hypothesis for Testing Answer-Set Programs

Though testing is the prevalent means to find errors in traditional software development, this subject has been addressed for ASP only recently (Janhunen et al. 2010; 2011; Febbraro et al. 2011). In particular, the small-scope hypothesis in traditional testing states that a high proportion of errors can be found by testing a program for all test inputs that are taken from some relatively small scope (Jackson and Damon 1996), i. e., by restricting the number of objects a test input is composed of. This suggests that it can be quite effective to test a program exhaustively for some restricted small scope instead of deliberately selecting test inputs from a larger one. A small-scope hypothesis in ASP would be a matter of interest for two reasons. First, it would allow to devise effective testing methods for uniform problem encodings (the prevailing representation mode ASP is used). For illustration, assume we encoded by means of ASP, using the rules below, the graph problem of testing whether a graph is disconnected, where problem instances are represented by facts over an input signature with predicates edge/2 and node/1: In software testing, the small-scope hypothesis states that a high proportion of errors can be found by testing a program for all test inputs within some small scope. In this paper, we evaluate the small-scope hypothesis for answer-set programming (ASP). To this end, we follow work in traditional testing and base our evaluation on mutation analysis. In fact, we show that a rather limited scope is sufficient for testing ASP encodings from a representative set of benchmark problems. Our experimental evaluation facilitates effective methods for testing in ASP. Also, it gives some justification to analyse programs at the propositional level after grounding them over a small domain.

Authors

• Johannes Oetsch
• Michael Prischink
• Jörg Pührer
• Martin Schwengerer
• Hans Tompits Stefan Woltran

Keywords

No keywords are indexed for this paper.