2 Search Results for "Banbara, Mutsunori"

Document
DOI: 10.4230/LIPIcs.CPM.2023.17
Encoding Hard String Problems with Answer Set Programming

Authors: Dominik Köppl

Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

Abstract
Despite the simple, one-dimensional nature of strings, several computationally hard problems on strings are known. Tackling hard problems beyond sizes of toy instances with straight-forward solutions is infeasible. To solve these problems on datasets of even small sizes, effort has to be put into the conception of algorithms leveraging profound characteristics of the input. Finding these characteristics can be eased by rapidly creating and evaluating prototypes of new concepts in how to tackle hard problems. Such a rapid-prototyping method for hard problems is answer set programming (ASP). In this light, we study the application of ASP on five NP-hard optimization problems in the field of strings. We provide MAX-SAT and ASP encodings, and empirically reason about the merits and flaws when working with ASP solvers.
Cite as

Dominik Köppl. Encoding Hard String Problems with Answer Set Programming. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{koppl:LIPIcs.CPM.2023.17,
  author =	{K\"{o}ppl, Dominik},
  title =	{{Encoding Hard String Problems with Answer Set Programming}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.17},
  URN =		{urn:nbn:de:0030-drops-179711},
  doi =		{10.4230/LIPIcs.CPM.2023.17},
  annote =	{Keywords: optimization problems, answer set programming, MAX-SAT encoding, NP-hard string problems}
}
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-dev.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)}
}
  • Refine by Author
  • 1 Banbara, Mutsunori
  • 1 Inoue, Katsumi
  • 1 Köppl, Dominik
  • 1 Tamura, Naoyuki

  • Refine by Classification
  • 1 Computing methodologies → Artificial intelligence
  • 1 Hardware → Theorem proving and SAT solving
  • 1 Theory of computation
  • 1 Theory of computation → Discrete optimization

  • Refine by Keyword
  • 1 Answer Set Programming
  • 1 Constraint Programming
  • 1 Event-Sequence Testing
  • 1 MAX-SAT encoding
  • 1 Matrix Model
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact