Banbara, Mutsunori ;
Tamura, Naoyuki ;
Inoue, Katsumi
Generating EventSequence Test Cases by Answer Set Programming with the Incidence Matrix
Abstract
The effective use of ASP solvers is essential for enhancing efficiency and scalability. The incidence matrix is a simple representation used in Constraint Programming (CP) and Integer Linear Programming for modeling combinatorial problems. Generating test cases for eventsequence testing is to find a sequence covering array (SCA). In this paper, we consider the problem of finding optimal sequence covering arrays by ASP and CP. Our approach is based on an effective combination of ASP solvers and the incidence matrix. We first present three CP models from different viewpoints of sequence covering arrays: the naïve matrix model, the eventposition matrix model, and the incidence matrix model. Particularly, in the incidence matrix model, an SCA can be represented by a (0,1)matrix called the incidence matrix of the array in which the coverage constraints of the given SCA can be concisely expressed. We then present an ASP program of the incidence matrix model. It is compact and faithfully reflects the original constraints of the incidence matrix model. In our experiments, we were able to significantly improve the previously known bounds for many arrays of strength three. Moreover, we succeeded either in finding optimal solutions or in improving known bounds for some arrays of strength four.
BibTeX  Entry
@InProceedings{banbara_et_al:LIPIcs:2012:3612,
author = {Mutsunori Banbara and Naoyuki Tamura and Katsumi Inoue},
title = {{Generating EventSequence Test Cases by Answer Set Programming with the Incidence Matrix}},
booktitle = {Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
pages = {8697},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897439},
ISSN = {18688969},
year = {2012},
volume = {17},
editor = {Agostino Dovier and V{\'i}tor Santos Costa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3612},
URN = {urn:nbn:de:0030drops36127},
doi = {http://dx.doi.org/10.4230/LIPIcs.ICLP.2012.86},
annote = {Keywords: EventSequence Testing, Answer Set Programming, Matrix Model, Constraint Programming, Propositional Satisfiability (SAT)}
}
Keywords: 

EventSequence Testing, Answer Set Programming, Matrix Model, Constraint Programming, Propositional Satisfiability (SAT) 
Seminar: 

Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)

Issue date: 

2012 
Date of publication: 

27.07.2012 