The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
The complexity of logic-based abduction
Open accessAbstract
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 subset-minimality, minimal cardinality, minimal weight, or minimality under prioritization of individual hypotheses. This paper presents a comprehensive complexity analysis of relevant decision and search problems related to abduction on propositional theories. Our results indicate that abduction is harder than deduction. In particular, we show that with the most basic forms of abduction the relevant decision problems are complete for complexity classes at the second level of the polynomial hierarchy, while the use of prioritization raises the complexity to the third level in certain cases.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
(1988) · Cited by 16,582
Lecture Notes in Artificial Intelligence
Brézillon, P., & Bouquet, P. (1999) · Cited by 7,473
Reiter, R. (1980) · Artificial Intelligence · doi:10.1016/0004-3702(80)90014-4 · Cited by 3,892
Probabilistic Reasoning in Intelligent Systems
(1988) · Elsevier eBooks · doi:10.1016/c2009-0-27609-4 · Cited by 3,321
A theory of diagnosis from first principles
Reiter, R. (1987) · Artificial Intelligence · doi:10.1016/0004-3702(87)90062-2 · Cited by 3,031
Philosophical Writings of Peirce
Peirce, C. S., & Buchler, J. (1955) · Medical Entomology and Zoology · Cited by 2,803
Fusion, propagation, and structuring in belief networks
Pearl, J. (1986) · Artificial Intelligence · doi:10.1016/0004-3702(86)90072-x · Cited by 2,127
The computational complexity of probabilistic inference using bayesian belief networks
Cooper, G. F. (1990) · Artificial Intelligence · doi:10.1016/0004-3702(90)90060-d · Cited by 1,937
de Kleer, J. (1986) · Artificial Intelligence · doi:10.1016/0004-3702(86)90080-9 · Cited by 1,736
Hobbs, J. R., Stickel, M. E., Appelt, D. E., & Martin, P. (1993) · Artificial Intelligence · doi:10.1016/0004-3702(93)90015-4 · Cited by 1,223
A new method for solving hard satisfiability problems
Selman, B., Levesque, H. J., & Mitchell, D. G. M. (1992) · Cited by 1,156
Doyle, J. (1979) · Artificial Intelligence · doi:10.1016/0004-3702(79)90008-0 · Cited by 1,132
Semantical considerations on nonmonotonic logic
Moore, R. C. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90042-6 · Cited by 1,122
Introduction to artificial intelligence
(2011) · Choice Reviews Online · doi:10.5860/choice.49-0903 · Cited by 1,085
Collected Papers of Charles Sanders Peirce.
N., E., Hartshorne, C., & Weiss, P. (1934) · The Journal of Philosophy · doi:10.2307/2015395 · Cited by 1,069
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90114-1 · Cited by 1,054
Linear-time algorithms for testing the satisfiability of propositional horn formulae
Dowling, W. F., & Gallier, J. H. (1984) · The Journal of Logic Programming · doi:10.1016/0743-1066(84)90014-1 · Cited by 1,013
McDermott, D., & Doyle, J. (1980) · Artificial Intelligence · doi:10.1016/0004-3702(80)90012-0 · Cited by 904
Word problems requiring exponential time(Preliminary Report)
Stockmeyer, L. J., & Meyer, A. R. (1973) · Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73 · doi:10.1145/800125.804029 · Cited by 871
A logical framework for default reasoning
Poole, D. (1988) · Artificial Intelligence · doi:10.1016/0004-3702(88)90077-x · Cited by 715
Collected Papers of Charles Sanders Peirce.
N., E., Hartshorne, C., & Weiss, P. (1934) · The Journal of Philosophy · doi:10.2307/2016224 · Cited by 581
A Catalog of Complexity Classes
JOHNSON, D. S. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50007-2 · Cited by 556
Abductive Inference Models for Diagnostic Problem-Solving
Peng, Y., & Reggia, J. A. (1990) · Springer eBooks · doi:10.1007/978-1-4419-8682-5 · Cited by 504
The complexity of optimization problems
Krentel, M. W. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90039-6 · Cited by 441
McDermott, D. (1982) · Journal of the ACM · doi:10.1145/322290.322293 · Cited by 407
The computational complexity of abduction
Bylander, T., Allemang, D., Tanner, M. C., & Josephson, J. R. (1991) · Artificial Intelligence · doi:10.1016/0004-3702(91)90005-5 · Cited by 406
Lifschitz, V. (1985) · International Joint Conference on Artificial Intelligence · Cited by 385
On the complexity of propositional knowledge base revision, updates, and counterfactuals
Eiter, T., & Gottlob, G. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90018-s · Cited by 349
Self-citationComplexity Results for Nonmonotonic Logics
Gottlob, G. (1992) · Journal of Logic and Computation · doi:10.1093/logcom/2.3.397 · Cited by 342
Self-citationOn the semantics of updates in databases
Fagin, R., Ullman, J. D., & Vardi, M. Y. (1983) · ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS) · doi:10.1145/588058.588100 · Cited by 338
Handbook of theoretical computer science
Czerbo, D. B. (1992) · Artificial Intelligence in Medicine · doi:10.1016/0933-3657(92)90044-p · Cited by 338
On the mechanization of abductive logic
Pople, H. E. (1973) · International Joint Conference on Artificial Intelligence · Cited by 284
Nonmonotonic Reasoning: Logical Foundations of Commonsense
Brewka, G. (1991) · Publikationsdatenbank der Fraunhofer-Gesellschaft (Fraunhofer-Gesellschaft) · Cited by 264
On the Relationship Between Abduction and Deduction
Console, L., Dupré, D. T., & Torasso, P. (1991) · Journal of Logic and Computation · doi:10.1093/logcom/1.5.661 · Cited by 240
A spectrum of logical definitions of model‐based diagnosis1
CONSOLE, L., & TORASSO, P. (1991) · Computational Intelligence · doi:10.1111/j.1467-8640.1991.tb00388.x · Cited by 236
Ginsberg, M. L. (1986) · Artificial Intelligence · doi:10.1016/0004-3702(86)90067-6 · Cited by 218
Explanation and prediction: an architecture for default and abductive reasoning
Poole, D. (1989) · Computational Intelligence · doi:10.1111/j.1467-8640.1989.tb00319.x · Cited by 212
Database Updates through Abduction
Kakas, A. C., & Mancarella, P. (1990) · CINECA IRIS Institutial research information system (University of Pisa) · Cited by 205
Normality and faults in logic-based diagnosis
Poole, D. (1989) · International Joint Conference on Artificial Intelligence · Cited by 178
A knowledge-level account of abduction
Levesque, H. J. (1989) · International Joint Conference on Artificial Intelligence · Cited by 167
Propositional circumscription and extended closed-world reasoning are ΠP2-complete
Eiter, T., & Gottlob, G. (1993) · Theoretical Computer Science · doi:10.1016/0304-3975(93)90073-3 · Cited by 164
Self-citationA survey of complexity results for non-monotonic logics
Cadoli, M., & Schaerf, M. (1993) · The Journal of Logic Programming · doi:10.1016/0743-1066(93)90029-g · Cited by 154
A Mechanism for Forming Composite Explanatory Hypotheses
Josephson, J. R., Chandrasekaran, B., Smith, J. W., & Tanner, M. C. (1987) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1987.4309060 · Cited by 144
A theory of diagnosis for incomplete causal models
Console, L., Dupré, D. T., & Torasso, P. (1989) · Institutional Research Information System University of Turin (University of Turin) · Cited by 135
Exploiting constraints in design synthesis
Finger, J. (1987) · Cited by 130
Abduction versus closure in causal theories
Konolige, K. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90073-7 · Cited by 111
Modal logic for default reasoning
Marek, W., & Truszczyński, M. (1990) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/bf01531081 · Cited by 63
Generalizations of Opt P to the polynomial hierarchy
Krentel, M. W. (1992) · Theoretical Computer Science · doi:10.1016/0304-3975(92)90073-o · Cited by 49
Computational complexity of hypothesis assembly
Allemang, D., Tanner, M. C., Bylander, T., & Josephson, J. R. (1987) · International Joint Conference on Artificial Intelligence · Cited by 45
Cited by
Complexity and expressive power of logic programming
Dantsin, E., Eiter, T., Gottlob, G., & Voronkov, A. (2001) · ACM Computing Surveys · doi:10.1145/502807.502810 · Cited by 739
Self-citationAbductive reasoning in logistics research
Kovács, G., & Spens, K. M. (2005) · International Journal of Physical Distribution & Logistics Management · doi:10.1108/09600030510590318 · Cited by 688
Logic programming and knowledge representation
Baral, C., & Gelfond, M. (1994) · The Journal of Logic Programming · doi:10.1016/0743-1066(94)90025-6 · Cited by 431
Coherence as constraint satisfaction
Thagard, P. (1998) · Cognitive Science · doi:10.1016/s0364-0213(99)80033-0 · Cited by 352
A content analysis of research approaches in logistics research
Spens, K. M., & Kovács, G. (2006) · International Journal of Physical Distribution & Logistics Management · doi:10.1108/09600030610676259 · Cited by 299
Metadata
- Authors
- Eiter, T., & Gottlob, G.
- Venue
- Journal of the ACM
- Published
- 1995-01-03
- Volume
- 42
- Issue
- 1
- Pages
- 3-42
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2100657934
- Cited by
- 422
- References
- 50
- FWCI
- 10.05
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.