Institut für Informatik und Computational Science
Refine
Has Fulltext
- no (31)
Year of publication
Document Type
- Article (31) (remove)
Language
- English (31)
Is part of the Bibliography
- yes (31)
Keywords
- answer set programming (4)
- Answer Set Programming (3)
- Answer set programming (3)
- Boolean logic models (1)
- Combinatorial multi-objective optimization (1)
- Complex optimization (1)
- Incremental answer set programming (1)
- Logic programming (1)
- Meta-Programming (1)
- Nonmonotonic reasoning (1)
- Preference Handling (1)
- Signaling transduction networks (1)
- Systems biology (1)
- Theory (1)
- action and change (1)
- acyclicity properties (1)
- automated guided vehicle routing (1)
- automated planning (1)
- bioinformatics (1)
- car assembly operations (1)
- competition (1)
- consistency (1)
- declarative problem solving (1)
- diagnosis (1)
- finite model computation (1)
- knowledge representation and nonmonotonic reasoning (1)
- logic-based modeling (1)
- loop formulas (1)
- proof complexity (1)
- satisfiability (1)
- stable model semantics (1)
- tableau calculi (1)
- technical notes and rapid communications (1)
- unfounded sets (1)
Institute
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.
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.
We introduce formal proof systems based on tableau methods for analyzing computations in Answer Set Programming (ASP). Our approach furnishes fine-grained instruments for characterizing operations as well as strategies of ASP solvers. The granularity is detailed enough to capture a variety of propagation and choice methods of algorithms used for ASP solving, also incorporating SAT-based and conflict-driven learning approaches to some extent. This provides us with a uniform setting for identifying and comparing fundamental properties of ASP solving approaches. In particular, we investigate their proof complexities and show that the run-times of best-case computations can vary exponentially between different existing ASP solvers. Apart from providing a framework for comparing ASP solving approaches, our characterizations also contribute to their understanding by pinning down the constitutive atomic operations. Furthermore, our framework is flexible enough to integrate new inference patterns, and so to study their relation to existing ones. To this end, we generalize our approach and provide an extensible basis aiming at a modular incorporation of additional language constructs. This is exemplified by augmenting our basic tableau methods with cardinality constraints and disjunctions.
Answer set programming (ASP) does not allow for incrementally constructing answer sets or locally validating constructions like proofs by only looking at a part of the given program. In this article, we elaborate upon an alternative approach to ASP that allows for incremental constructions. Our approach draws its basic intuitions from the area of default logics. We investigate the feasibility of the concept of semi-monotonicity known from default logics as a basis of incrementality. On the one hand, every logic program has at least one answer set in our alternative setting, which moreover can be constructed incrementally based on generating rules. On the other hand, the approach may produce answer sets lacking characteristic properties of standard answer sets, such as being a model of the given program. We show how integrity constraints can be used to re-establish such properties, even up to correspondence with standard answer sets. Furthermore, we develop an SLD-like proof procedure for our incremental approach to ASP, which allows for query-oriented computations. Also, we provide a characterization of our definition of answer sets via a modification of Clarks completion. Based on this notion of program completion, we present an algorithm for computing the answer sets of a logic program in our approach.