TY - JOUR
A1 - Gebser, Martin
A1 - Kaufmann, Benjamin
A1 - Schaub, Torsten
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 - http://dx.doi.org/10.1016/j.artint.2012.04.001
SN - 0004-3702 (print)
VL - 187
IS - 8
SP - 52
EP - 89
PB - Elsevier
CY - Amsterdam
ER -
TY - JOUR
A1 - Delgrande, James
A1 - Schaub, Torsten
A1 - Tompits, Hans
A1 - Woltran, Stefan
T1 - A model-theoretic approach to belief change in answer set programming
JF - ACM transactions on computational logic
N2 - We address the problem of belief change in (nonmonotonic) logic programming under answer set semantics. Our formal techniques are analogous to those of distance-based belief revision in propositional logic. In particular, we build upon the model theory of logic programs furnished by SE interpretations, where an SE interpretation is a model of a logic program in the same way that a classical interpretation is a model of a propositional formula. Hence we extend techniques from the area of belief revision based on distance between models to belief change in logic programs.
We first consider belief revision: for logic programs P and Q, the goal is to determine a program R that corresponds to the revision of P by Q, denoted P * Q. We investigate several operators, including (logic program) expansion and two revision operators based on the distance between the SE models of logic programs. It proves to be the case that expansion is an interesting operator in its own right, unlike in classical belief revision where it is relatively uninteresting. Expansion and revision are shown to satisfy a suite of interesting properties; in particular, our revision operators satisfy all or nearly all of the AGM postulates for revision.
We next consider approaches for merging a set of logic programs, P-1,...,P-n. Again, our formal techniques are based on notions of relative distance between the SE models of the logic programs. Two approaches are examined. The first informally selects for each program P-i those models of P-i that vary the least from models of the other programs. The second approach informally selects those models of a program P-0 that are closest to the models of programs P-1,...,P-n. In this case, P-0 can be thought of as a set of database integrity constraints. We examine these operators with regards to how they satisfy relevant postulate sets.
Last, we present encodings for computing the revision as well as the merging of logic programs within the same logic programming framework. This gives rise to a direct implementation of our approach in terms of off-the-shelf answer set solvers. These encodings also reflect the fact that our change operators do not increase the complexity of the base formalism.
KW - Theory
KW - Answer set programming
KW - belief revision
KW - belief merging
KW - program encodings
KW - strong equivalence
Y1 - 2013
U6 - http://dx.doi.org/10.1145/2480759.2480766
SN - 1529-3785 (print)
VL - 14
IS - 2
PB - Association for Computing Machinery
CY - New York
ER -
TY - JOUR
A1 - Gebser, Martin
A1 - Kaufmann, Benjamin
A1 - Kaminski, Roland
A1 - Ostrowski, Max
A1 - Schaub, Torsten
A1 - Schneider, Marius
T1 - Potassco the Potsdam answer set solving collection
JF - AI communications : AICOM ; the European journal on artificial intelligence
N2 - This paper gives an overview of the open source project Potassco, the Potsdam Answer Set Solving Collection, bundling tools for Answer Set Programming developed at the University of Potsdam.
KW - Answer set programming
KW - declarative problem solving
Y1 - 2011
U6 - http://dx.doi.org/10.3233/AIC-2011-0491
SN - 0921-7126 (print)
VL - 24
IS - 2
SP - 107
EP - 124
PB - IOS Press
CY - Amsterdam
ER -
TY - JOUR
A1 - Fichte, Johannes Klaus
A1 - Szeider, Stefan
T1 - Backdoors to tractable answer set programming
JF - Artificial intelligence
N2 - Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many Al problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable.
In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent "clever reasoning shortcuts" through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming. (C) 2015 Elsevier B.V. All rights reserved.
KW - Answer set programming
KW - Backdoors
KW - Computational complexity
KW - Parameterized complexity
KW - Kernelization
Y1 - 2015
U6 - http://dx.doi.org/10.1016/j.artint.2014.12.001
SN - 0004-3702 (print)
SN - 1872-7921 (online)
VL - 220
SP - 64
EP - 103
PB - Elsevier
CY - Amsterdam
ER -
TY - JOUR
A1 - Videla, Santiago
A1 - Guziolowski, Carito
A1 - Eduati, Federica
A1 - Thiele, Sven
A1 - Gebser, Martin
A1 - Nicolas, Jacques
A1 - Saez-Rodriguez, Julio
A1 - Schaub, Torsten
A1 - Siegel, Anne
T1 - Learning Boolean logic models of signaling networks with ASP
JF - Theoretical computer science
N2 - Boolean networks provide a simple yet powerful qualitative modeling approach in systems biology. However, manual identification of logic rules underlying the system being studied is in most cases out of reach. Therefore, automated inference of Boolean logical networks from experimental data is a fundamental question in this field. This paper addresses the problem consisting of learning from a prior knowledge network describing causal interactions and phosphorylation activities at a pseudo-steady state, Boolean logic models of immediate-early response in signaling transduction networks. The underlying optimization problem has been so far addressed through mathematical programming approaches and the use of dedicated genetic algorithms. In a recent work we have shown severe limitations of stochastic approaches in this domain and proposed to use Answer Set Programming (ASP), considering a simpler problem setting. Herein, we extend our previous work in order to consider more realistic biological conditions including numerical datasets, the presence of feedback-loops in the prior knowledge network and the necessity of multi-objective optimization. In order to cope with such extensions, we propose several discretization schemes and elaborate upon our previous ASP encoding. Towards real-world biological data, we evaluate the performance of our approach over in silico numerical datasets based on a real and large-scale prior knowledge network. The correctness of our encoding and discretization schemes are dealt with in Appendices A-B. (C) 2014 Elsevier B.V. All rights reserved.
KW - Answer set programming
KW - Signaling transduction networks
KW - Boolean logic models
KW - Combinatorial multi-objective optimization
KW - Systems biology
Y1 - 2015
U6 - http://dx.doi.org/10.1016/j.tcs.2014.06.022
SN - 0304-3975 (print)
SN - 1879-2294 (online)
VL - 599
SP - 79
EP - 101
PB - Elsevier
CY - Amsterdam
ER -