How complicated is the set of stable models of a recursive logic program?
type: Item
instance of: scholarly article
title: How complicated is the set of stable models of a recursive logic program?
zbMATH Open document ID: 0766.03024
DOI: 10.1016/0168-0072(92)90069-C
published in: Annals of Pure and Applied Logic
publication date: 1992-09-27T00:00:00Z
review text: The notion of a stable model of a logic program was introduced by Gelfond and Lifschitz (1988). The present paper establishes that the set of all stable models in a Herbrand universe of a recursive logic program is, up to recursive renaming, the set of all infinite paths of a recursive, countably branching tree, and conversely. As a consequence, the problem, given a recursive logic program, of determining whether it has a stable model, is \(\Sigma^ 1_ 1\)-complete.
Mathematics Subject Classification ID: 03D35
Mathematics Subject Classification ID: 68N17
Mathematics Subject Classification ID: 03C50
zbMATH DE Number: 60747
zbMATH Keywords: stable model of a logic program
zbMATH Keywords: Herbrand universe
zbMATH Keywords: recursive logic program
zbMATH Keywords: branching tree
author: Wiktor Marek
author: Jeffrey Remmel
author: Anil Nerode
MaRDI profile type: Publication
cites work: Q3960112
cites work: Q4385536
cites work: Q3477998
cites work: General logical databases and programs: Default logic semantics and stratification
cites work: Q4146722
cites work: A theory of nonmonotonic rule systems I
cites work: A theory of nonmonotonic rule systems. II
cites work: The relationship between stable, supported, default and autoepistemic semantics for general logic programs
cites work: Q3477931
cites work: A logic for default reasoning
cites work: Q5573961
cites work: Monadic Elementary Formal Systems
cites work: The Semantics of Predicate Logic as a Programming Language
description: scientific article; zbMATH DE number 60747