Some computational aspects of circumscription
DOI10.1145/78935.78936zbMATH Open0697.68085OpenAlexW2007880598WikidataQ129039380 ScholiaQ129039380MaRDI QIDQ3474909FDOQ3474909
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
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
nonmonotonic reasoningfirst-order logicundecidabilitycircumscriptionmodel-checkingHorn clausesNP- completeness
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35)
Cited In (26)
- Circumscribing embedded implications (without stratifications)
- Title not available (Why is that?)
- Reconsideration of circumscriptive induction with pointwise circumscription
- An incremental algorithm for generating all minimal models
- On compact representations of propositional circumscription
- Computing protected circumscription
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- The complexity of theorem proving in circumscription and minimal entailment
- On the counting complexity of propositional circumscription
- Computing circumscription revisited: A reduction algorithm
- Reasoning with minimal models: efficient algorithms and applications
- On the computability of circumscription
- An extension of pointwise circumscription
- Annotation theories over finite graphs
- The complexity of model checking for circumscriptive formulae
- Title not available (Why is that?)
- On the tractability of minimal model computation for some CNF theories
- Definability by constant-depth polynomial-size circuits
- Computation with Narrow CTCs
- The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
- The complexity of propositional closed world reasoning and circumscription
- A theorem on the consistency of circumscription
- Conservative query normalization on parallel circumscription
- Graph-based construction of minimal models
- Recursively indefinite databases
- COMPLEXITY OF UNIVERSAL 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)
