The computational complexity of structure-based causality
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 87507414
- Type
- D - Journal article
- DOI
-
10.1613/jair.5229
- Title of journal
- Journal Artificial Intelligence Research
- Article number
- -
- First page
- 431
- Volume
- 58
- Issue
- -
- ISSN
- 1076-9757
- Open access status
- Compliant
- Month of publication
- February
- Year of publication
- 2017
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
-
- Citation count
- 2
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This work states and formally proves important complexity results for structure-based causality and the related notions of responsibility and blame, and introduces a new hierarchy of complexity classes D^P_k of independent interest, together with natural problems complete for these classes. Causality and related notions are used in many areas, including software fault localisation, root cause analysis, plane crashes. These complexity results direct the applications towards approximations and/or restrictions to most influential (higher responsibility) causes. Existing applications include verification, software engineering and neural networks classifications. This work was presented by Chockler as a keynote at CREST ETAPS 2016.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -