| 1. |
- Oetsch, Johannes, et al.
(författare)
-
Program correspondence under the answer-set semantics : The non-ground case
- 2008
-
Ingår i: Logic Programming. - Berlin, Heidelberg : Springer. - 3540899812 - 9783540899815 ; , s. 591-605
-
Konferensbidrag (refereegranskat)abstract
- The study of various notions of equivalence between logic programs in the area of answer-set programming (ASP) gained increasing interest in recent years. The main reason for this undertaking is that ordinary equivalence between answer-set programs fails to yield a replacement property similar to the one of classical logic. Although many refined program correspondence notions have been introduced in the ASP literature so far, most of these notions were studied for propositional programs only, which limits their practical usability as concrete programming applications require the use of variables. In this paper, we address this issue and introduce a general framework for specifying parameterised notions of program equivalence for non-ground disjunctive logic programs under the answer-set semantics. Our framework is a generalisation of a similar one defined previously for the propositional case and allows the specification of several equivalence notions extending well-known ones studied for propositional programs. We provide semantic characterisations for instances of our framework generalising uniform equivalence, and we study decidability and complexity aspects. Furthermore, we consider axiomatisations of such correspondence problems by means of polynomial translations into second-order logic.
|
|
| 2. |
- Schulte, Christian, et al.
(författare)
-
Dynamic Analysis of Bounds Versus Domain Propagation
- 2008
-
Ingår i: LOGIC PROGRAMMING, PROCEEDINGS. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783540899815 ; , s. 332-346
-
Konferensbidrag (refereegranskat)abstract
- Constraint propagation solvers interleave propagation (removing impossible values from variable domains) with search. Previously, Schulte and Stuckey introduced the use of static analysis to determine where in a constraint program domain propagators can be replaced by more efficient bounds propagators and still ensure that the same search) is traversed. This paper introduces a dynamic,yet considerably simpler approach to uncover the same information. The information is obtained by a linear time traversal of an analysis graph that straightforwardly, v reflects the properties of propagators implementing constraints. Experiments confirm that the simple, dynamic method is efficient and that it can be used interleaved with search, taking advantage of the simplification of the constraint graph that arises from search.
|
|
