الفهرس 
chapter 1Only 14 pages are availabe for public view
 |  | from | 133 |  |  |
| | | from | 133 | | |
Abstract
English Summary
Answer Set Programming (ASP) is a knowledge representation paradigm related to the areas of declarative logic programming and nonmonotonic reasoning . In ASP, a problem is represented as a logic program whose models under the answer semantics constitute solutions (answer set). Answer sets have been defined by Gelfond and Lifschitz as a generalization of their definition into stable model semantics. The concept of answer set was originally proposed as a semantics for negation as failure in prolog. In contrast to traditional prolog systems, where solutions are computed by query-answering, answer sets are computed by model-oriented solvers, called answer set solvers.
The practical applications of ASP comes from various fields, such as graph theory, planning, diagnosis, bounded model checking, wire routing problems, and query answering. However, classical ASP and query-orientation appear to be completely diametrical. Related to the fact that answer set semantics does neither support ”relevance” nor ”modularity”. The principle of relevance states that the truth value of an atom only depends on the subprogram connected to this atom in the underlying dependency graph. Accordingly, modularity stipulates that the semantics of an overall program can be composed of the semantics of its subprograms (connected in the dependency graph). As a consequence, the existence of answer set for a logic program is neither guaranteed, nor parts of an answer set be constructed from only subset of the given program.
In this thesis, we investigated an approach to ASP that allows for query oriented computations. In particular, we are interested in fixed-points construction, incremental construction and modularity.
• We elaborated upon an approach to answer set programming that allows for fixed-points construction. This study introduced the concept of justified answer set, which are characterized by fixed-points constructions and their applied rules. Our approach draws the basic intuitions from the area of default logics. In particular, our approach investigated in how far the concept of semi-monotonicity can serve as feasible basis of fixed points. Every logic program has at least one justified answer set that can be constructed by fixed-points constructions.
• Our study modified the definition of incremental answer sets, yielding another way to re-establish some properties. Namely, we introduced the concept of stable answer sets. Every logic program has at least one stable answer set, which can be constructed incrementally based on applicable rules. As a result, there is a one-to-one correspondence between the stable answer sets and the maximal normal alternating fixed points of logic programs. Stable answer sets semantics are thus equivalent to the following variants of answer set semantics:
regular model semantics,
partial stable model semantics,
preferential semantics,
semantics of maximal three-valued models and
stable class semantics.
• We introduced a sound and complete theorem proving method for our incremental approach to answer set programming, which allows for query-oriented computations.
This thesis contains four chapter as follows:
Chapter 1 provides background information on the area of answer set programming. We gave an informal overview of logic programming. We elaborated on answer set programming. We introduced the related concepts of well-founded semantics and regular model semantics for logic programs. We described the relationship between nonmonotonic reasoning and declarative logic programming. Finally, we introduced incremental answer set programming.
Chapter 2 introduces an approach to answer set programming. We introduced some basic concepts and justified answer sets. We elaborated upon the formal properties of our justified approach. The relationship between justified answer sets and classical answer sets of logic program, between justified answer sets and incremental answer sets, between justified answer sets and well-founded semantics for logic programs discussed . Finally, we showed that there is a one-to-one correspondence between justified answer sets and justified extensions.
chapter 3 introduces the concept of stable answer sets as another approach to answer set programming. The fundamental idea is to refine the definition of incremental answer sets in a way re-establishing some properties of answer sets, such as containing programs well-founded sets. We introduced stable answer sets. We elaborated upon their formal properties. We described the relationships to classical answer sets and incremental answer sets of logic programs. We showed that stable answer sets are in a one-to-one correspondence with the regular sets of logic programs. We showed that every stable answer set of a program is an extension of its well-founded set.
Chapter 4 presents a sound and complete theorem proving method for our incremental approach to answer set programming, which allows for query-oriented computations. We introduced the concept of a stable proof. Furthermore, we interested in checking whether a given query is satisfied by some stable answer set. We provided a calculus along with the concept of a derivation.
It is worth mentioning that two papers from thesis published in two different journals, the first put in chapter 2 and the second put in chapter3.