On finitely recursive programs

Details On finitely recursive programs On finitely recursive programs

2009-01-19

arxiv.org/abs/0901.2850v1

Theory and Practice of Logic Programming, 9(2), 213-238, 2009

Computer Science

Artificial Intelligence

26 pages, Preliminary version in Proc. of ICLP 2007, Best paper award

Scientific paper

Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties, for example ground queries are decidable while in the general case the stable model semantics is highly undecidable. In this paper we prove that a larger class of programs, called finitely recursive programs, preserves most of the good properties of finitary programs under the stable model semantics, namely: (i) finitely recursive programs enjoy a compactness property; (ii) inconsistency checking and skeptical reasoning are semidecidable; (iii) skeptical resolution is complete for normal finitely recursive programs. Moreover, we show how to check inconsistency and answer skeptical queries using finite subsets of the ground program instantiation. We achieve this by extending the splitting sequence theorem by Lifschitz and Turner: We prove that if the input program P is finitely recursive, then the partial stable models determined by any smooth splitting omega-sequence converge to a stable model of P.

Affiliated with

Also associated with

No associations

Rating

On finitely recursive 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 finitely recursive programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On finitely recursive programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-566755