How complicated is the set of stable models of a recursive logic program?

DOI10.1016/0168-0072(92)90069-CzbMath0766.03024MaRDI QIDQ1192346

Anil Nerode, Victor W. Marek, Jeffery B. Remmel

Publication date: 27 September 1992

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

branching treeHerbrand universerecursive logic programstable model of a logic program

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Logic programming (68N17) Models with special properties (saturated, rigid, etc.) (03C50)

Related Items

A context for belief revision: forward chaining-normal nonmonotonic rule systems, Index Sets for Finite Normal Predicate Logic Programs with Function Symbols, Invertible classes, A theory of nonmonotonic rule systems. II, The expressiveness of locally stratified programs, Complexity and undecidability results for logic programming, On the computational cost of disjunctive logic programming: Propositional case, A topological characterization of the stable and minimal model classes of propositional logic programs, $\mathbb{FDNC}$ : Decidable Non-monotonic Disjunctive Logic Programs with Function Symbols, Annotated nonmonotonic rule systems, My work with Victor Marek: a mathematician looks at answer set programming, On the Continuity of Gelfond-Lifschitz Operator and Other Applications of Proof-Theory in ASP

Cites Work

• A logic for default reasoning
• General logical databases and programs: Default logic semantics and stratification
• The relationship between stable, supported, default and autoepistemic semantics for general logic programs
• A theory of nonmonotonic rule systems. II
• A theory of nonmonotonic rule systems I
• The Semantics of Predicate Logic as a Programming Language
• Monadic Elementary Formal Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item