An Efficient and Flexible Engine for Computing Fixed Points

Details An Efficient and Flexible Engine for Computing Fixed Points An Efficient and Flexible Engine for Computing Fixed Points

2004-12-09

arxiv.org/abs/cs/0412041v2

Computer Science

Programming Languages

26 pages

Scientific paper

An efficient and flexible engine for computing fixed points is critical for many practical applications. In this paper, we firstly present a goal-directed fixed point computation strategy in the logic programming paradigm. The strategy adopts a tabled resolution (or memorized resolution) to mimic the efficient semi-naive bottom-up computation. Its main idea is to dynamically identify and record those clauses that will lead to recursive variant calls, and then repetitively apply those alternatives incrementally until the fixed point is reached. Secondly, there are many situations in which a fixed point contains a large number or even infinite number of solutions. In these cases, a fixed point computation engine may not be efficient enough or feasible at all. We present a mode-declaration scheme which provides the capabilities to reduce a fixed point from a big solution set to a preferred small one, or from an infeasible infinite set to a finite one. The mode declaration scheme can be characterized as a meta-level operation over the original fixed point. We show the correctness of the mode declaration scheme. Thirdly, the mode-declaration scheme provides a new declarative method for dynamic programming, which is typically used for solving optimization problems. There is no need to define the value of an optimal solution recursively, instead, defining a general solution suffices. The optimal value as well as its corresponding concrete solution can be derived implicitly and automatically using a mode-directed fixed point computation engine. Finally, this fixed point computation engine has been successfully implemented in a commercial Prolog system. Experimental results are shown to indicate that the mode declaration improves both time and space performances in solving dynamic programming problems.

Affiliated with

Also associated with

No associations

Rating

An Efficient and Flexible Engine for Computing Fixed Points 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 An Efficient and Flexible Engine for Computing Fixed Points, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient and Flexible Engine for Computing Fixed Points will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-451945