Some computational aspects of circumscription

DOI10.1145/78935.78936MaRDI QIDQ3474909zbMATH OpenOpenAlexWikidataFDO

Authors Phokion G. Kolaitis, Christos Papadimitriou

Publication date 1990

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/78935.78936

zbMATH Keywords

circumscriptionfirst-order logicHorn clausesmodel-checkingnonmonotonic reasoningNP- completenessundecidability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the computability of circumscription
• Computing circumscription revisited: A reduction algorithm
• An algorithm to compute circumscription
• scientific article; zbMATH DE number 1189101
• On the counting complexity of propositional circumscription
• The complexity of circumscription in DLs
• Computing circular separability
• Computing protected circumscription
• COMPLEXITY OF UNIVERSAL CIRCUMSCRIPTION
• On the satisfiability of circumscription

Cited in

(29)

• On the computability of circumscription
• Reasoning with minimal models: efficient algorithms and applications
• The complexity of model checking for circumscriptive formulae
• The complexity of propositional closed world reasoning and circumscription
• Computing circumscription revisited: A reduction algorithm
• On compact representations of propositional circumscription
• Graph-based construction of minimal models
• Annotation theories over finite graphs
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• An incremental algorithm for generating all minimal models
• An extension of pointwise circumscription
• scientific article; zbMATH DE number 1696843 (Why is no real title available?)
• Computation with Narrow CTCs
• scientific article; zbMATH DE number 994057 (Why is no real title available?)
• The complexity of theorem proving in circumscription and minimal entailment
• scientific article; zbMATH DE number 4210121 (Why is no real title available?)
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• Computing protected circumscription
• Definability by constant-depth polynomial-size circuits
• scientific article; zbMATH DE number 35418 (Why is no real title available?)
• Circumscribing embedded implications (without stratifications)
• COMPLEXITY OF UNIVERSAL CIRCUMSCRIPTION
• General domain circumscription and its first-order reduction
• On the tractability of minimal model computation for some CNF theories
• Conservative query normalization on parallel circumscription
• A theorem on the consistency of circumscription
• Recursively indefinite databases
• Reconsideration of circumscriptive induction with pointwise circumscription
• On the counting complexity of propositional circumscription

This page was built for publication: Some computational aspects of circumscription

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