Generalized closed world assumption is \(\Pi ^ 0_ 2\)-complete

DOI10.1016/0020-0190(90)90012-MzbMath0695.68064MaRDI QIDQ910251

V. S. Subrahmanian, Jan Chomicki

Publication date: 1990

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

zbMATH Keywords

undecidabilitynegationlogic programmingarithmetical hierarchynon-Horn logic programs

Mathematics Subject Classification ID

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

Related Items

Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, On the computational cost of disjunctive logic programming: Propositional case, Computing minimal models by partial instantiation, Expressive power and complexity of partial models for disjunctive deductive databases

Cites Work

• Decidability and definability with circumscription
• Inferring negative information from disjunctive databases
• On the relationship between circumscription and negation as failure
• Deduction in non-Horn databases
• Weak generalized closed world assumption
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item