Some computational aspects of circumscription

DOI10.1145/78935.78936MaRDI QIDQ3474909zbMATHOpenAlexWikidataFDO

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

nonmonotonic reasoningfirst-order logicundecidabilitycircumscriptionmodel-checkingHorn clausesNP- completeness

Mathematics Subject Classification ID

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

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

(26)

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