DROPS

Document

DOI: 10.4230/LIPIcs.ICLP.2012.86

Generating Event-Sequence Test Cases by Answer Set Programming with the Incidence Matrix

Authors: Mutsunori Banbara, Naoyuki Tamura, and Katsumi Inoue

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)

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 event-sequence 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 event-position 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.

Cite as

Mutsunori Banbara, Naoyuki Tamura, and Katsumi Inoue. Generating Event-Sequence Test Cases by Answer Set Programming with the Incidence Matrix. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 86-97, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{banbara_et_al:LIPIcs.ICLP.2012.86,
  author =	{Banbara, Mutsunori and Tamura, Naoyuki and Inoue, Katsumi},
  title =	{{Generating Event-Sequence Test Cases by Answer Set Programming with the Incidence Matrix}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{86--97},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.86},
  URN =		{urn:nbn:de:0030-drops-36127},
  doi =		{10.4230/LIPIcs.ICLP.2012.86},
  annote =	{Keywords: Event-Sequence Testing, Answer Set Programming, Matrix Model, Constraint Programming, Propositional Satisfiability (SAT)}
}

Search Results

Documents authored by Tamura, Naoyuki

Generating Event-Sequence Test Cases by Answer Set Programming with the Incidence Matrix

Abstract

Cite as

Thanks for your feedback!

Could not send message