Reasoning with infinite stable models

This paper illustrates extensively the theoretical properties, the implementation issues, and the programming style underlying finitary programs. They are a class of normal logic programs whose consequences under the stable model semantics can be effectively computed, despite the fact that finitary...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2004-06, Vol.156 (1), p.75-111
Main Author: Bonatti, Piero A.
Format: Article
Language:English
Subjects:
Answer set programming
Finitary programs
First-order nonmonotonic reasoning
Infinite domains
Logic programming
Stable model semantics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper illustrates extensively the theoretical properties, the implementation issues, and the programming style underlying finitary programs. They are a class of normal logic programs whose consequences under the stable model semantics can be effectively computed, despite the fact that finitary programs admit function symbols (hence infinite domains) and recursion. From a theoretical point of view, finitary programs are interesting because they enjoy properties that are extremely unusual for a nonmonotonic formalism, such as compactness. From the application point of view, the theory of finitary programs shows how the existing technology for answer set programming can be extended from problem solving below the second level of the polynomial hierarchy to all semidecidable problems. Moreover, finitary programs allow a more natural encoding of recursive data structures and may increase the performance of credulous reasoners.
ISSN:0004-3702
1872-7921
DOI:10.1016/j.artint.2004.02.001