Hard problems for simple default logics

DOI10.1016/0004-3702(91)90011-8zbMATH Open0736.68044OpenAlexW2148718809MaRDI QIDQ1182166FDOQ1182166

Authors: Henry Kautz, Bart Selman 

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

Recommendations

• Publication:3493327
• The Complexity of Reasoning for Fragments of Default Logic
• scientific article
• scientific article; zbMATH DE number 408811

zbMATH Keywords

complexity of reasoningdefault logicsIVP-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Cites Work

• Title not available (Why is that?)
• Model-preference default theories
• A logic for default reasoning
• A skeptical theory of inheritance in nonmonotonic semantic networks
• Title not available (Why is that?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (43)

• Reasoning with power defaults
• Title not available (Why is that?)
• Querying disjunctive databases through nonmonotonic logics
• Is intractability of nonmonotonic reasoning a real drawback?
• Outlier detection using default reasoning
• Support set selection for abductive and default reasoning
• Title not available (Why is that?)
• Title not available (Why is that?)
• Limited reasoning in first-order knowledge bases
• Default Rules in the Logic of First-Degree Entailments
• Modeling simultaneous events with default reasoning and tight derivations
• Title not available (Why is that?)
• On the computational cost of disjunctive logic programming: Propositional case
• Propositional semantics for disjunctive logic programs
• A decision method for nonmonotonic reasoning based on autoepistemic reasoning
• Propositional default logics made easier: computational complexity of model checking.
• Efficient query processing with reduced implicate tries
• Tractable reasoning via approximation
• Default reasoning from conditional knowledge bases: Complexity and tractable cases
• Defaults and relevance in model-based reasoning
• The complexity of path-based defeasible inheritance
• Default reasoning by deductive planning
• Complexity of Default Logic on Generalized Conjunctive Queries
• Title not available (Why is that?)
• Default theories that always have extensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted default theories: expressive power and outlier detection tasks
• Resolving ambiguity in nonmonotonic inheritance hierarchies
• Title not available (Why is that?)
• Outlier detection for simple default theories
• Proof complexity of propositional default logic
• Semantics and complexity of abduction from default theories
• Default reasoning using classical logic
• Model-preference default theories
• Privacy preservation using multi-context systems and default logic
• Yet some more complexity results for default logic
• The complexity of propositional closed world reasoning and circumscription
• Title not available (Why is that?)
• Title not available (Why is that?)
• Skeptical reasoning in FC-normal logic programs is \(\Pi_1^1\)-complete
• On the impact of stratification on the complexity of nonmonotonic reasoning
• The Complexity of Reasoning for Fragments of Default Logic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1182166)