Complexity and undecidability results for logic programming

DOI10.1007/BF01536398zbMath0858.68015MaRDI QIDQ1924779

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)

Related Items (4)

Circumscribing DATALOG: expressive power and complexity ⋮ Abduction from logic programs: Semantics and complexity ⋮ Active integrity constraints for general-purpose knowledge bases ⋮ Expressive power and complexity of partial models for disjunctive deductive databases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidability and definability with circumscription
• Tie-breaking semantics and structural totality
• The expressive power of stratified logic programs
• Fixed-point extensions of first-order logic
• Circumscription - a form of non-monotonic reasoning
• The mathematics of non-monotonic reasoning
• 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
• Formalizing a logic for logic programming
• Structure and complexity of relational queries
• The expressiveness of locally stratified programs
• A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
• A kripke-kleene semantics for logic programs*
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Negation as failure. II
• Relational queries computable in polynomial time
• Negation in logic programming
• Contributions to the Theory of Logic Programming
• The Semantics of Predicate Logic as a Programming Language
• A survey of complexity results for non-monotonic logics
• Commonsense axiomatizations for logic programs
• Autoepistemic logic
• The well-founded semantics for general logic programs
• The Stable Models of a Predicate Logic Program

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