License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2023.17
URN: urn:nbn:de:0030-drops-179711
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17971/
Köppl, Dominik
Encoding Hard String Problems with Answer Set Programming
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.
BibTeX - Entry
@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.dagstuhl.de/opus/volltexte/2023/17971},
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}
}
