TY - JOUR A1 - Bomanson, Jori A1 - Janhunen, Tomi A1 - Schaub, Torsten H. A1 - Gebser, Martin A1 - Kaufmann, Benjamin T1 - Answer Set Programming Modulo Acyclicity JF - Fundamenta informaticae N2 - Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the state-of-the-art ASP solver CLASP. The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving. Y1 - 2016 U6 - https://doi.org/10.3233/FI-2016-1398 SN - 0169-2968 SN - 1875-8681 VL - 147 SP - 63 EP - 91 PB - IOS Press CY - Amsterdam ER - TY - JOUR A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Neumann, André A1 - Schaub, Torsten H. T1 - Clasp : a conflict-driven answer set solver Y1 - 2007 SN - 978-3-540- 72199-4 ER - TY - JOUR A1 - Banbara, Mutsunori A1 - Kaufmann, Benjamin A1 - Ostrowski, Max A1 - Schaub, Torsten H. T1 - Clingcon: The next generation JF - Theory and practice of logic programming KW - Constraint Answer Set Programming (CASP) KW - Answer Set Programming (ASP) KW - Sat Modulo Theories (SMT) KW - Constraint Programming (CP) Y1 - 2017 U6 - https://doi.org/10.1017/S1471068417000138 SN - 1471-0684 SN - 1475-3081 VL - 17 SP - 408 EP - 461 PB - Cambridge Univ. Press CY - New York ER - TY - JOUR A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Neumann, André A1 - Schaub, Torsten H. T1 - Conflict-driven answer set enumeration Y1 - 2007 SN - 978-3-540- 72199-4 ER - TY - JOUR A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Neumann, André A1 - Schaub, Torsten H. T1 - Conflict-driven answer set solving Y1 - 2007 SN - 978-1-57735-323-2 ER - TY - JOUR A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Schaub, Torsten H. T1 - Conflict-driven answer set solving: From theory to practice JF - Artificial intelligence N2 - We introduce an approach to computing answer sets of logic programs, based on concepts successfully applied in Satisfiability (SAT) checking. The idea is to view inferences in Answer Set Programming (ASP) as unit propagation on nogoods. This provides us with a uniform constraint-based framework capturing diverse inferences encountered in ASP solving. Moreover, our approach allows us to apply advanced solving techniques from the area of SAT. As a result, we present the first full-fledged algorithmic framework for native conflict-driven ASP solving. Our approach is implemented in the ASP solver clasp that has demonstrated its competitiveness and versatility by winning first places at various solver contests. KW - Answer set programming KW - Logic programming KW - Nonmonotonic reasoning Y1 - 2012 U6 - https://doi.org/10.1016/j.artint.2012.04.001 SN - 0004-3702 VL - 187 IS - 8 SP - 52 EP - 89 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Kaufmann, Benjamin A1 - Leone, Nicola A1 - Perri, Simona A1 - Schaub, Torsten H. T1 - Grounding and Solving in Answer Set Programming JF - AI magazine N2 - Answer set programming is a declarative problem-solving paradigm that rests upon a work flow involving modeling, grounding, and solving. While the former is described by Gebser and Schaub (2016), we focus here on key issues in grounding, or how to systematically replace object variables by ground terms in an effective way, and solving, or how to compute the answer sets, of a propositional logic program obtained by grounding. Y1 - 2016 SN - 0738-4602 VL - 37 SP - 25 EP - 32 PB - Association for the Advancement of Artificial Intelligence CY - Menlo Park ER - TY - THES A1 - Kaufmann, Benjamin T1 - High performance answer set solving Y1 - 2015 ER - TY - JOUR A1 - Gebser, Martin A1 - Kaminski, Roland A1 - Kaufmann, Benjamin A1 - Schaub, Torsten H. T1 - Multi-shot ASP solving with clingo JF - Theory and practice of logic programming N2 - We introduce a new flexible paradigm of grounding and solving in Answer Set Programming (ASP), which we refer to as multi-shot ASP solving, and present its implementation in the ASP system clingo. Multi-shot ASP solving features grounding and solving processes that deal with continuously changing logic programs. In doing so, they remain operative and accommodate changes in a seamless way. For instance, such processes allow for advanced forms of search, as in optimization or theory solving, or interaction with an environment, as in robotics or query answering. Common to them is that the problem specification evolves during the reasoning process, either because data or constraints are added, deleted, or replaced. This evolutionary aspect adds another dimension to ASP since it brings about state changing operations. We address this issue by providing an operational semantics that characterizes grounding and solving processes in multi-shot ASP solving. This characterization provides a semantic account of grounder and solver states along with the operations manipulating them. The operative nature of multi-shot solving avoids redundancies in relaunching grounder and solver programs and benefits from the solver's learning capacities. clingo accomplishes this by complementing ASP's declarative input language with control capacities. On the declarative side, a new directive allows for structuring logic programs into named and parameterizable subprograms. The grounding and integration of these subprograms into the solving process is completely modular and fully controllable from the procedural side. To this end, clingo offers a new application programming interface that is conveniently accessible via scripting languages. By strictly separating logic and control, clingo also abolishes the need for dedicated systems for incremental and reactive reasoning, like iclingo and oclingo, respectively, and its flexibility goes well beyond the advanced yet still rigid solving processes of the latter. Y1 - 2018 U6 - https://doi.org/10.1017/S1471068418000054 SN - 1471-0684 SN - 1475-3081 VL - 19 IS - 1 SP - 27 EP - 82 PB - Cambridge Univ. Press CY - New York ER - TY - JOUR A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Schaub, Torsten H. T1 - Multi-threaded ASP solving with clasp JF - Theory and practice of logic programming N2 - We present the new multi-threaded version of the state-of-the-art answer set solver clasp. We detail its component and communication architecture and illustrate how they support the principal functionalities of clasp. Also, we provide some insights into the data representation used for different constraint types handled by clasp. All this is accompanied by an extensive experimental analysis of the major features related to multi-threading in clasp. Y1 - 2012 U6 - https://doi.org/10.1017/S1471068412000166 SN - 1471-0684 VL - 12 IS - 8 SP - 525 EP - 545 PB - Cambridge Univ. Press CY - New York ER -