Complexity and undecidability results for logic programming

DOI10.1007/BF01536398MaRDI QIDQ1924779zbMATH OpenFDO

Authors John S. Schlipf

Publication date 25 March 1997

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

Full work available at URL https://doi.org/10.1007/BF01536398

zbMATH Keywords

degree of uncomputabilityexpressive power

Mathematics Subject Classification ID

Logic programming (68N17)

Recommendations

• The expressive powers of the logic programming semantics
• The well-founded semantics for general logic programs
• Complexity results for abductive logic programming
• scientific article; zbMATH DE number 2085278

Cites work

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

Cited in

(32)

• Circumscribing DATALOG: expressive power and complexity
• Expressive power and complexity of partial models for disjunctive deductive databases
• Generalized disjunctive well-founded semantics for logic programs.
• Abduction from logic programs: Semantics and complexity
• Monadic logic programs and functional complexity
• Active integrity constraints for general-purpose knowledge bases
• The expressive powers of the logic programming semantics
• Complexity of computing with extended propositional logic programs
• A connection between the Cantor-Bendixson derivative and the well-founded semantics of finite logic programs
• Logic programming: laxness and saturation
• scientific article; zbMATH DE number 4130360 (Why is no real title available?)
• scientific article; zbMATH DE number 4130365 (Why is no real title available?)
• scientific article; zbMATH DE number 3872671 (Why is no real title available?)
• scientific article; zbMATH DE number 4199630 (Why is no real title available?)
• scientific article; zbMATH DE number 4147557 (Why is no real title available?)
• Decidable Fragments of Logic Programming with Value Invention
• scientific article; zbMATH DE number 3903964 (Why is no real title available?)
• scientific article; zbMATH DE number 4043305 (Why is no real title available?)
• scientific article; zbMATH DE number 4103047 (Why is no real title available?)
• scientific article; zbMATH DE number 139622 (Why is no real title available?)
• The complexity of revising logic programs
• scientific article; zbMATH DE number 517063 (Why is no real title available?)
• scientific article; zbMATH DE number 732053 (Why is no real title available?)
• Decidability of logic program semantics and applications to testing
• Decidability of the Clark's completion semantics for monadic programs and queries
• scientific article; zbMATH DE number 218508 (Why is no real title available?)
• scientific article; zbMATH DE number 2085278 (Why is no real title available?)
• scientific article; zbMATH DE number 1389855 (Why is no real title available?)
• Game characterizations of logic program properties
• Some undecidable properties of SOS specifications
• The expressive power of revised Datalog on problems with closure properties
• Bounded nondeterminism of logic programs

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)