DROPS

Document

DOI: 10.4230/LIPIcs.ICLP.2012.323

On the Termination of Logic Programs with Function Symbols

Authors: Sergio Greco, Francesca Spezzano, and Irina Trubitsyna

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)

Abstract

Recently there has been an increasing interest in the bottom-up evaluation of the semantics of logic programs with complex terms. The main problem due to the presence of functional symbols in the head of rules is that the corresponding ground program could be infinite and that finiteness of models and termination of the evaluation procedure is not guaranteed. This paper introduces, by deeply analyzing program structure, new decidable criteria, called safety and Gamma-acyclicity, for checking termination of logic programs with function symbols under bottom-up evaluation. These criteria guarantee that stable models are finite and computable, as it is possible to generate a finitely ground program equivalent to the source program. We compare new criteria with other decidable criteria known in the literature and show that the Gamma-acyclicity criterion is the most general one. We also discuss its application in answering bound queries.

Cite as

Sergio Greco, Francesca Spezzano, and Irina Trubitsyna. On the Termination of Logic Programs with Function Symbols. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 323-333, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{greco_et_al:LIPIcs.ICLP.2012.323,
  author =	{Greco, Sergio and Spezzano, Francesca and Trubitsyna, Irina},
  title =	{{On the Termination of Logic Programs with Function Symbols}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{323--333},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.323},
  URN =		{urn:nbn:de:0030-drops-36335},
  doi =		{10.4230/LIPIcs.ICLP.2012.323},
  annote =	{Keywords: Logic Programming, Function Symbols, Bottom-up Execution, Program Termination, Stable Models}
}

Search Results

Documents authored by Greco, Sergio

On the Termination of Logic Programs with Function Symbols

Abstract

Cite as

Thanks for your feedback!

Could not send message