Hard problems for simple default logics

DOI10.1016/0004-3702(91)90011-8zbMath0736.68044OpenAlexW2148718809MaRDI QIDQ1182166

Bart Selman, Henry A. Kautz

Publication date: 28 June 1992

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(91)90011-8

zbMATH Keywords

complexity of reasoningdefault logicsIVP-completeness

Mathematics Subject Classification ID

Related Items (27)

The complexity of propositional closed world reasoning and circumscription ⋮ Default theories that always have extensions ⋮ Privacy Preservation Using Multi-context Systems and Default Logic ⋮ Limited reasoning in first-order knowledge bases ⋮ A decision method for nonmonotonic reasoning based on autoepistemic reasoning ⋮ Querying disjunctive databases through nonmonotonic logics ⋮ Default reasoning by deductive planning ⋮ Outlier detection using default reasoning ⋮ Default reasoning using classical logic ⋮ Efficient query processing with reduced implicate tries ⋮ Defaults and relevance in model-based reasoning ⋮ On the computational cost of disjunctive logic programming: Propositional case ⋮ Propositional semantics for disjunctive logic programs ⋮ Support set selection for abductive and default reasoning ⋮ Is intractability of nonmonotonic reasoning a real drawback? ⋮ On the impact of stratification on the complexity of nonmonotonic reasoning ⋮ Outlier detection for simple default theories ⋮ Semantics and complexity of abduction from default theories ⋮ Restricted default theories: expressive power and outlier detection tasks ⋮ Default Rules in the Logic of First-Degree Entailments ⋮ Resolving ambiguity in nonmonotonic inheritance hierarchies ⋮ The complexity of path-based defeasible inheritance ⋮ The Complexity of Reasoning for Fragments of Default Logic ⋮ Default reasoning from conditional knowledge bases: Complexity and tractable cases ⋮ Propositional default logics made easier: computational complexity of model checking. ⋮ Tractable reasoning via approximation ⋮ Yet some more complexity results for default logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A logic for default reasoning
• A skeptical theory of inheritance in nonmonotonic semantic networks
• Model-preference default theories
• Linear-time algorithms for testing the satisfiability of propositional horn formulae

This page was built for publication: Hard problems for simple default logics