Termination Prediction for General Logic Programs

Simple item page
dc.creatorShen, Yi-Dong
dc.creatorDe Schreye, Danny
dc.creatorVoets, Dean
dc.date2009-05-13
dc.date.accessioned2026-07-07T13:14:25Z
dc.date.available2026-07-07T13:14:25Z
dc.descriptionWe 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.
dc.description28 pages, 12 figures. to appear in Theory and Practice of Logic Programming (TPLP)
dc.identifierhttps://arxiv.org/abs/0905.2004
dc.identifierhttp://arxiv.org/abs/0905.2004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/230205
dc.subjectProgramming Languages
dc.subjectArtificial Intelligence
dc.subjectLogic in Computer Science
dc.titleTermination Prediction for General Logic Programs
dc.typetext

Files

Collections

arXiv