Termination Prediction for General Logic Programs

Details Termination Prediction for General Logic Programs Termination Prediction for General Logic Programs

2009-05-13

arxiv.org/abs/0905.2004v1

Computer Science

Programming Languages

28 pages, 12 figures. to appear in Theory and Practice of Logic Programming (TPLP)

Scientific paper

We present a heuristic framework for attacking the undecidable termination problem of logic programs, as an alternative to current termination/non-termination proof approaches. We introduce an idea of termination prediction, which predicts termination of a logic program in case that neither a termination nor a non-termination proof is applicable. We establish a necessary and sufficient characterization of infinite (generalized) SLDNF-derivations with arbitrary (concrete or moded) queries, and develop an algorithm that predicts termination of general logic programs with arbitrary non-floundering queries. We have implemented a termination prediction tool and obtained quite satisfactory experimental results. Except for five programs which break the experiment time limit, our prediction is 100% correct for all 296 benchmark programs of the Termination Competition 2007, of which eighteen programs cannot be proved by any of the existing state-of-the-art analyzers like AProVE07, NTI, Polytool and TALP.

Affiliated with

Also associated with

No associations

Rating

Termination Prediction for General 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 Termination Prediction for General Logic Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Termination Prediction for General Logic Programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-128548