Title: Polynomial interpretations as a basis for termination analysis of logic programs
Authors: Nguyen, Manh Thang ×
De Schreye, Danny #
Issue Date: 2005
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:3668 pages:311-325
Conference: Twenty First International Conference on Logic Programming location:Sitges (Barcelona), Spain date:October 2-5, 2005
Abstract: This paper introduces a new technique for termination analysis of definite logic programs based on polynomial interpretations. The principle of this technique is to map each function and predicate symbol to a polynomial over some domain of natural numbers, like it has been done in proving termination of term rewriting systems. Such polynomial interpretations can be seen as a direct generalisation of the traditional techniques in termination analysis of LPs, where (semi-) linear norms and level mappings are used. Our extension generalises these to arbitrary polynomials. We extend a number of standard concepts and results on termination analysis to the context of polynomial interpretations. We propose a constraint based approach for automatically generating polynomial interpretations that satisfy termination conditions.
ISBN: 3-540-29208-X
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
ToICLP2005-final.pdf Published 155KbAdobe PDFView/Open


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

© Web of science