Complexity Results for Default Reasoning from Conditional Knowledge Bases
<p>Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form \"<em>phi->psi</em>\", which informally read as \"generally, if <em>phi</em> then <em>psi</em>\". Su...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Morgan Kaufmann
2000
|
| _version_ | 1797084349799071744 |
|---|---|
| author | Eiter, T Lukasiewicz, T |
| author_facet | Eiter, T Lukasiewicz, T |
| author_sort | Eiter, T |
| collection | OXFORD |
| description | <p>Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form \"<em>phi->psi</em>\", which informally read as \"generally, if <em>phi</em> then <em>psi</em>\". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their algorithmic properties only partial results are known so far. In this paper, we fill these gaps and draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base <em>KB</em> and a default \"<em>phi->psi</em>\", does <em>KB</em> entail \"<em>phi->psi</em>\"? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment). We consider the general propositional case as well as syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). Furthermore, we analyze the effect of precomputing rankings for the respective approaches. Our results complement and extend previous results, and contribute in exploring the tractability / intractability frontier of default reasoning from conditional knowledge bases.</p> |
| first_indexed | 2024-03-07T01:54:15Z |
| format | Conference item |
| id | oxford-uuid:9b2d0be7-aa94-4fd5-a12f-bb6064aa23bc |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:54:15Z |
| publishDate | 2000 |
| publisher | Morgan Kaufmann |
| record_format | dspace |
| spelling | oxford-uuid:9b2d0be7-aa94-4fd5-a12f-bb6064aa23bc2022-03-27T00:26:50ZComplexity Results for Default Reasoning from Conditional Knowledge BasesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:9b2d0be7-aa94-4fd5-a12f-bb6064aa23bcDepartment of Computer ScienceMorgan Kaufmann2000Eiter, TLukasiewicz, T<p>Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form \"<em>phi->psi</em>\", which informally read as \"generally, if <em>phi</em> then <em>psi</em>\". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their algorithmic properties only partial results are known so far. In this paper, we fill these gaps and draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base <em>KB</em> and a default \"<em>phi->psi</em>\", does <em>KB</em> entail \"<em>phi->psi</em>\"? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment). We consider the general propositional case as well as syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). Furthermore, we analyze the effect of precomputing rankings for the respective approaches. Our results complement and extend previous results, and contribute in exploring the tractability / intractability frontier of default reasoning from conditional knowledge bases.</p> |
| spellingShingle | Eiter, T Lukasiewicz, T Complexity Results for Default Reasoning from Conditional Knowledge Bases |
| title | Complexity Results for Default Reasoning from Conditional Knowledge Bases |
| title_full | Complexity Results for Default Reasoning from Conditional Knowledge Bases |
| title_fullStr | Complexity Results for Default Reasoning from Conditional Knowledge Bases |
| title_full_unstemmed | Complexity Results for Default Reasoning from Conditional Knowledge Bases |
| title_short | Complexity Results for Default Reasoning from Conditional Knowledge Bases |
| title_sort | complexity results for default reasoning from conditional knowledge bases |
| work_keys_str_mv | AT eitert complexityresultsfordefaultreasoningfromconditionalknowledgebases AT lukasiewiczt complexityresultsfordefaultreasoningfromconditionalknowledgebases |