Alternate document: Details The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions (93) Thomas Eiter, Georg Gottlob |
Alternate document: Details Complexity Aspects of Various Semantics for Disjunctive Databases (93) Thomas Eiter, Georg Gottlob |
Alternate document: Details Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics (93) Thomas Eiter |
(Enter summary)
Abstract: Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about logic-based abduction. Candidates for abductive explanations are usually subjected to minimality criteria such as subsetminimality, minimal cardinality, minimal weight, or minimality under prioritization of individual hypotheses. This paper presents a comprehensive complexity analysis of... (Update)
Cited by: More
An Abduction-based Method for Index - Relaxation In Taxonomy-Based (2003)
(Correct)
A Unifying Framework for Flexible Information - Access In Taxonomy-Based (2004)
(Correct)
Espoo 2003 HUT-TCS-A85 - Testing The Equivalence
(Correct)
Active bibliography (related documents): More All
0.6: A Survey on Complexity Results for Non-monotonic Logics - Cadoli, Schaerf (1993)
(Correct)
0.6: On the Complexity of Propositional Knowledge Base Revision.. - Eiter, Gottlob (1992)
(Correct)
0.6: The Complexity of Nested Counterfactuals and Iterated.. - Eiter, Gottlob (1993)
(Correct)
Similar documents based on text: More All
0.6: Thomas Eiter and Heikki Mannila - Christian Doppler Labor
(Correct)
0.6: Identifying the Minimal Transversals of a Hypergraph and.. - Eiter, Gottlob (1991)
(Correct)
0.5: Publication List 1998 - Informationssysteme, Wien (1998)
(Correct)
Related documents from co-citation: More All
25: A Logic for Default Reasoning (context) - Reiter - 1980
21: Complexity Results for Nonmonotonic Logics (context) - Gottlob - 1992
20: A Catalog of Complexity Classes (context) - Johnson - 1990
BibTeX entry: (Update)
Eiter, T., and G. Gottlob. 1992a. The Complexity of Logic-Based Abduction. http://citeseer.ist.psu.edu/eiter93complexity.html More
@inproceedings{ eiter93complexity,
author = "Thomas Eiter and Georg Gottlob",
title = "The Complexity of Logic-Based Abduction",
booktitle = "Symposium on Theoretical Aspects of Computer Science",
pages = "70-79",
year = "1993",
url = "citeseer.ist.psu.edu/eiter93complexity.html" }
Citations (may not include all citations):
3985
Computers and Intractability -- A Guide to the Theory of NP-.. (context) - Garey, Johnson - 1979
823
A Logic for Default Reasoning (context) - Reiter - 1980 ACM DBLP
726
Probabilistic Reasoning in Intelligent Systems (context) - Pearl - 1988 ACM
444
A Theory of Diagnosis From First Principles (context) - Reiter - 1987 ACM DBLP
409
A New Method for Solving Hard Satisfiability Problems
- Selman, Levesque et al. - 1992 DBLP
321
A Truth-Maintenance System (context) - Doyle - 1979
300
Semantical Considerations on Nonmonotonic Logics (context) - Moore - 1985
278
The computational complexity of probabilistic inference usin.. (context) - Cooper - 1990 DBLP
275
Interpretation as Abduction
- Hobbs, Stickel et al. - 1988 ACM DBLP
250
A Logical Framework for Default Reasoning (context) - Poole - 1988 ACM DBLP
187
Linear-time Algorithms for Testing the Satisfiability of Pro.. (context) - Dowling, Gallier - 1984
162
Computing Circumscription (context) - Lifschitz - 1985 ACM DBLP
158
Complexity Results for Nonmonotonic Logics (context) - Gottlob - 1992 DBLP
149
Introduction to Artificial Intelligence (context) - Charniak, McDermott - 1985 ACM
148
The Complexity of Optimization Problems (context) - Krentel - 1988 ACM DBLP
138
Information Processing Letters (context) - Blumer, Ehrenfeucht et al. - 1987
117
the Relationship Between Abduction and Deduction
- Console, Dupr'e et al. - 1991
113
Non-Monotonic Logic (context) - McDermott, Doyle - 1980
109
Database Updates Through Abduction (context) - Kakas, Mancarella - 1990 ACM DBLP
105
Bounded query classes (context) - Wagner - 1990 ACM DBLP
100
Word Problems Requiring Exponential Time (context) - Stockmeyer, Meyer - 1973
95
the Complexity of Propositional Knowledge Base Revision
- Eiter, Gottlob - 1992
95
the Semantics of Updates in Databases (context) - Fagin, Ullman et al. - 1983
90
Propositional Circumscription and Extended Closed World Reas..
- Eiter, Gottlob - 1993
89
Artificial Intelligence (context) - Ginsberg - 1986 ACM DBLP
89
Abductive Inference Models for Diagnostic Problem Solving (context) - Peng, Reggia - 1990
88
The computational complexity of abduction
- Bylander, Allemang et al. - 1991 ACM DBLP
88
Abductive Planning with Event Calculus (context) - Eshghi - 1988 DBLP
87
Explanation and Prediction: An Architecture for Default and ..
- Poole - 1989 ACM
86
Nonmonotonic Reasoning: Logical Foundations of Commonsense (context) - Brewka - 1991
85
Abductive and Default Reasoning: A Computational Core (context) - Selman, Levesque - 1990 DBLP
80
Normality and Faults in Logic Based Diagnosis
- Poole - 1989
80
A Spectrum of Logical Definitions of Model Based Diagnosis (context) - Console, Torasso - 1991
72
Belief Revision and Default Reasoning: Syntax-Based Approach..
- Nebel - 1991 DBLP
65
A knowledge-level account for abduction (context) - Levesque - 1989
65
Abduction versus closure in causal theories (context) - Konolige - 1992 ACM DBLP
64
The equivalence problem for regular expressions with squarin.. (context) - Meyer, Stockmeyer - 1972
64
and structuring in belief networks (context) - Pearl, propagation - 1986
62
An Assumption-Based Truth Maintenance System (context) - de Kleer - 1986
62
the Mechanization of Abductive Logic (context) - Pople - 1973
60
Non-Monotonic Logic II: Nonmonotonic Modal Theories (context) - McDermott - 1982
50
the Approximability of NP-complete Optimization Problems (context) - Kann - 1992
49
A Methodology for Using a Default and Abductive Reasoning Sy..
- Poole - 1989 ACM
49
Exploiting Constraints in Design Synthesis (context) - Finger - 1987 ACM
48
The Complexity of Propositional Default Logic (context) - Stillman - 1992
40
and Sparse Turing-Complete Sets for NP (context) - Kadin, NP et al. - 1989
38
A Neat Theory of Marker Passing (context) - Charniak - 1986 DBLP
37
General Diagnosis by Abductive Inference (context) - Cox, Pietrzykowski - 1987 DBLP
35
A Theory of Diagnosis for Incomplete Causal Models (context) - Console, Dupr'e et al. - 1989 DBLP
34
La Sapienza (context) - Cadoli, Schaerf et al. - 1992
29
the Greedy Algorithm for Satisfiability
- Koutsoupias, Papadimitriou - 1992
24
Annals of Mathematics and Artificial Intelligence (context) - Marek, Truszczy'nski et al. - 1990 ACM
24
A Mechanism for Forming Composite Explanatory Hypotheses (context) - Josephson, Chandrasekaran et al. - 1987
24
Generalizations of OptP to the Polynomial Hierarchy (context) - Krentel - 1992
22
Abduction and induction (context) - Peirce - 1955
20
On Using Oracles That Compute Values
- Fenner, Homer et al. - 1993 ACM DBLP
19
Computational Complexity of Hypothesis Assembly (context) - Allemang, Tanner et al. - 1987 DBLP
16
Some Results Concerning the Computational Complexity of Abdu.. (context) - Bylander, Allemang et al. - 1989 ACM DBLP
15
A Tractable Class of Abduction Problems (context) - Eshghi - 1993 DBLP
12
Hypothesis Generation by Machine (context) - Morgan - 1971 DBLP
11
and Nonmonotonic Equality (context) - Charniak, Abductive - 1988
9
Hypothesis Classification (context) - Friedrich, Gottlob et al. - 1990
9
the Complexity of Computing Optimal Solutions (context) - Chen, Toda - 1991
8
Inference in Text Understanding (context) - Norvig - 1987 DBLP
8
volume A of Handbook of Theoretical Computer Science (context) - Johnson, of et al. - 1990
8
The Monotonic Abduction Problem: A Functional Characterizati.. (context) - Bylander - 1991 DBLP
7
On Finding Extensions of Default Theories (context) - Papadimitriou, Sideri - 1992 ACM DBLP
6
The computational complexity of multiple-context truth maint.. (context) - Provan - 1990 DBLP
3
Complexity Classification in Truth Maintenance Systems (context) - Rutenburg - 1991
1
Logic Programs in Artificial Intelligence (context) - Kowalski - 1991
1
Approximate Inference for Concept Languages (context) - Cadoli, Schaerf - 1992
1
An Abductive Characterization of the TMS (context) - Giordano, Martelli - 1990 DBLP
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.kr.tuwien.ac.at/staff/eiter/1842-papers/): More
Complexity Aspects of Various Semantics for Disjunctive Databases - Eiter, Gottlob (1993)
(Correct)
Semantics and Complexity of Abduction from Default Theories - Eiter, Gottlob, Leone (1997)
(Correct)
Default Logic as a Query Language - Cadoli, Eiter, Gottlob (1997)
(Correct)
Online articles have much greater impact More about CiteSeer.IST Add search form to your site Submit documents Feedback
CiteSeer.IST - Copyright Penn State and NEC