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

The Complexity of Logic-Based Abduction (1993)  (Make Corrections)  (78 citations)
Thomas Eiter, Georg Gottlob
Symposium on Theoretical Aspects of Computer Science

  Home/Search   Context   Related

Links:   ACM   DBLP

 
View or download:
kr.tuwien.ac.at/staff/...cdtr9235.ps.gz
Cached:  PS.gz  PS  PDF  Image  Update  Help

From:  kr.tuwien.ac.at/staff/eiter/18... (more)
(Enter author homepages)

Rate this article: (best)
  Comment on this article  
(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