Complexity and undecidability results for logic programming

DOI10.1007/BF01536398zbMATH Open0858.68015MaRDI QIDQ1924779FDOQ1924779

John S. Schlipf

Publication date: 25 March 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

expressive powerdegree of uncomputability

Mathematics Subject Classification ID

Logic programming (68N17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The well-founded semantics for general logic programs
• Fixed-point extensions of first-order logic
• The Semantics of Predicate Logic as a Programming Language
• Autoepistemic logic
• Circumscription - a form of non-monotonic reasoning
• A kripke-kleene semantics for logic programs*
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Relational queries computable in polynomial time
• Negation in logic programming
• Contributions to the Theory of Logic Programming
• A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
• The mathematics of non-monotonic reasoning
• Structure and complexity of relational queries
• Decidability and definability with circumscription
• A survey of complexity results for non-monotonic logics
• Why not negation by fixpoint?
• How complicated is the set of stable models of a recursive logic program?
• A theory of nonmonotonic rule systems. II
• Tie-breaking semantics and structural totality
• The expressive power of stratified logic programs
• Formalizing a logic for logic programming
• Negation as failure. II
• The expressiveness of locally stratified programs
• The Stable Models of a Predicate Logic Program
• Commonsense axiomatizations for logic programs

Cited In (12)

• The expressive power of revised Datalog on problems with closure properties
• Logic programming: laxness and saturation
• Abduction from logic programs: Semantics and complexity
• Bounded nondeterminism of logic programs
• Expressive power and complexity of partial models for disjunctive deductive databases
• Title not available (Why is that?)
• Circumscribing DATALOG: expressive power and complexity
• Active integrity constraints for general-purpose knowledge bases
• The complexity of revising logic programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Complexity and undecidability results for logic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924779)