The complexity of propositional closed world reasoning and circumscription
From MaRDI portal
Publication:1329160
DOI10.1016/S0022-0000(05)80004-2zbMath0806.68096WikidataQ55980557 ScholiaQ55980557MaRDI QIDQ1329160
Marco Cadoli, Maurizio Lenzerini
Publication date: 13 February 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items
Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, Complexity of counting the optimal solutions, Logic and social cognition. The facts matter, and so do computational models, Combining answer set programming with description logics for the semantic web, Reasoning under minimal upper bounds in propositional logic, Circumscribing DATALOG: expressive power and complexity, On the computational cost of disjunctive logic programming: Propositional case, Abduction from logic programs: Semantics and complexity, Is intractability of nonmonotonic reasoning a real drawback?, Reasoning on with Defeasibility in ASP, Reducing belief revision to circumscription (and vice versa), Complexity of Counting the Optimal Solutions, Formalizing GDPR provisions in reified I/O logic: the DAPRECO knowledge base, A theoretical framework on proactive information exchange in agent teamwork, On the parameterized complexity of non-monotonic logics, The complexity of circumscriptive inference in Post's lattice, Trichotomies in the complexity of minimal inference, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Default reasoning from conditional knowledge bases: Complexity and tractable cases, On the computational complexity of assumption-based argumentation for default reasoning., On the complexity of data disjunctions., Backdoors to tractable answer set programming, Tractable reasoning via approximation, Constructing NP-intermediate problems by blowing holes with parameters of various properties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Querying logical databases
- Closed-world databases and circumscription
- Negation as failure: careful closure procedure
- A theory of diagnosis from first principles
- An algorithm to compute circumscription
- Eliminating the fixed predicates from a circumscription
- A circumscriptive theorem prover
- A logic for default reasoning
- Circumscription - a form of non-monotonic reasoning
- The decision problem for database dependencies
- Why not negation by fixpoint?
- The computational complexity of abduction
- Hard problems for simple default logics
- An efficient method for eliminating varying predicates from a circumscription
- The complexity of model checking for circumscriptive formulae
- Deduction in non-Horn databases
- Weak generalized closed world assumption
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Some computational aspects of circumscription
- Minimal consequence in sentential logic
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- On the Complexity of Timetable and Multicommodity Flow Problems
- A survey of complexity results for non-monotonic logics
- The complexity of satisfiability problems
