Generalized closed world assumption is ^ 0_ 2-complete

DOI10.1016/0020-0190(90)90012-MMaRDI QIDQ910251zbMATH OpenFDO

Authors Jan Chomicki, V. S. Subrahmanian

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90012-M

zbMATH Keywords

arithmetical hierarchylogic programmingnegationnon-Horn logic programsundecidability

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Hierarchies of computability and definability (03D55) Artificial intelligence (68T99)

Recommendations

• scientific article; zbMATH DE number 589696
• ECWA made easy
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Negation as failure: careful closure procedure
• Closed-world databases and circumscription

Cites work

• Decidability and definability with circumscription
• Deduction in non-Horn databases
• scientific article; zbMATH DE number 3872640 (Why is no real title available?)
• scientific article; zbMATH DE number 3874667 (Why is no real title available?)
• scientific article; zbMATH DE number 4092826 (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 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 4185011 (Why is no real title available?)
• Inferring negative information from disjunctive databases
• On the relationship between circumscription and negation as failure
• Weak generalized closed world assumption

Cited in

(8)

• Expressive power and complexity of partial models for disjunctive deductive databases
• ECWA made easy
• On the computational cost of disjunctive logic programming: Propositional case
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• scientific article; zbMATH DE number 589696 (Why is no real title available?)
• Annotations on the consistency of the closed world assumption
• Generalized well-founded semantics for logic programs
• Computing minimal models by partial instantiation

This page was built for publication: Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete

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