On the existence of stable models of non-stratified logic programs

Details On the existence of stable models of non-stratified logic programs On the existence of stable models of non-stratified logic programs

2004-12-23

arxiv.org/abs/cs/0412105v1

Computer Science

Artificial Intelligence

Scientific paper

This paper introduces a fundamental result, which is relevant for Answer Set programming, and planning. For the first time since the definition of the stable model semantics, the class of logic programs for which a stable model exists is given a syntactic characterization. This condition may have a practical importance both for defining new algorithms for checking consistency and computing answer sets, and for improving the existing systems. The approach of this paper is to introduce a new canonical form (to which any logic program can be reduced to), to focus the attention on cyclic dependencies. The technical result is then given in terms of programs in canonical form (canonical programs), without loss of generality. The result is based on identifying the cycles contained in the program, showing that stable models of the overall program are composed of stable models of suitable sub-programs, corresponding to the cycles, and on defining the Cycle Graph. Each vertex of this graph corresponds to one cycle, and each edge corresponds to onehandle, which is a literal containing an atom that, occurring in both cycles, actually determines a connection between them. In fact, the truth value of the handle in the cycle where it appears as the head of a rule, influences the truth value of the atoms of the cycle(s) where it occurs in the body. We can therefore introduce the concept of a handle path, connecting different cycles. If for every odd cycle we can find a handle path with certain properties, then the existence of stable model is guaranteed.

Affiliated with

Also associated with

No associations

Rating

On the existence of stable models of non-stratified logic programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the existence of stable models of non-stratified logic programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the existence of stable models of non-stratified logic programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93834