Some computational aspects of circumscription
From MaRDI portal
Publication:3474909
DOI10.1145/78935.78936zbMath0697.68085OpenAlexW2007880598WikidataQ129039380 ScholiaQ129039380MaRDI QIDQ3474909
Phokion G. Kolaitis, Christos H. 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
undecidabilityfirst-order logicmodel-checkingHorn clausesnonmonotonic reasoningcircumscriptionNP- completeness
Analysis of algorithms and problem complexity (68Q25) Undecidability and degrees of sets of sentences (03D35) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
The complexity of propositional closed world reasoning and circumscription ⋮ Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ Reconsideration of circumscriptive induction with pointwise circumscription ⋮ Reasoning with minimal models: efficient algorithms and applications ⋮ On compact representations of propositional circumscription ⋮ An extension of pointwise circumscription ⋮ An incremental algorithm for generating all minimal models ⋮ On the tractability of minimal model computation for some CNF theories ⋮ Recursively indefinite databases ⋮ The complexity of model checking for circumscriptive formulae ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Annotation theories over finite graphs ⋮ Conservative query normalization on parallel circumscription ⋮ Graph-based construction of minimal models
