Transformation-Based Bottom-Up Computation of the Well-Founded Model

Computer Science – Logic in Computer Science

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

43 pages, 3 figures

Scientific paper

We present a framework for expressing bottom-up algorithms to compute the well-founded model of non-disjunctive logic programs. Our method is based on the notion of conditional facts and elementary program transformations studied by Brass and Dix for disjunctive programs. However, even if we restrict their framework to nondisjunctive programs, their residual program can grow to exponential size, whereas for function-free programs our program remainder is always polynomial in the size of the extensional database (EDB). We show that particular orderings of our transformations (we call them strategies) correspond to well-known computational methods like the alternating fixpoint approach, the well-founded magic sets method and the magic alternating fixpoint procedure. However, due to the confluence of our calculi, we come up with computations of the well-founded model that are provably better than these methods. In contrast to other approaches, our transformation method treats magic set transformed programs correctly, i.e. it always computes a relevant part of the well-founded model of the original program.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Transformation-Based Bottom-Up Computation of the Well-Founded Model 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 Transformation-Based Bottom-Up Computation of the Well-Founded Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transformation-Based Bottom-Up Computation of the Well-Founded Model will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-125168

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.