2026-07-21T14:10:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17971 2024-03-06T11:00:45Z ddc:004 open_access

Encoding Hard String Problems with Answer Set Programming Köppl, Dominik optimization problems answer set programming MAX-SAT encoding NP-hard string problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dominik Köppl 2023 Is Part Of LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2023.17 urn:nbn:de:0030-drops-179711 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.17 eng https://creativecommons.org/licenses/by/4.0/legalcode