Title: Termination prediction for general logic programs
Authors: Shen, Yi-Dong ×
De Schreye, Danny
Voets, Dean #
Issue Date: Nov-2009
Publisher: Cambridge University Press
Series Title: Theory and Practice of Logic Programming vol:9 issue:6 pages:751-780
Abstract: We present an approximation 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 benchmark
programs of the Termination Competition 2007, of which eighteen programs cannot be
proved by the existing state-of-the-art analyzers like AProVE07, NTI, Polytool and TALP.
ISSN: 1471-0684
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
termination_prediction.pdfMain article Published 202KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science