Some computational aspects of circumscription

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

zbMATH Keywords

undecidabilityfirst-order logicmodel-checkingHorn clausesnonmonotonic reasoningcircumscriptionNP- completeness

Mathematics Subject Classification ID

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