Conference item
Complexity Results for Structure−Based Causality
- Abstract:
-
We analyze the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. In particular, we analyze the complexity of the sophisticated notions of weak and actual causality by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. To our knowledge, no complexity aspects of causal relationships have been considered so far, and our results shed light on this issue.
Actions
Authors
- Publisher:
- Morgan Kaufmann
- Host title:
- Proceedings of the 17th International Joint Conference on Artificial Intelligence‚ IJCAI 2001‚ Seattle‚ Washington‚ USA‚ August 4−10‚ 2001
- Publication date:
- 2001-01-01
- ISBN:
- 1558607773
- UUID:
-
uuid:124cfb3d-6932-44bf-b6af-3e96328694f7
- Local pid:
-
cs:6727
- Deposit date:
-
2015-03-31
- ARK identifier:
Terms of use
- Copyright date:
- 2001
If you are the owner of this record, you can report an update to it here: Report update to this record