Causal Theories of Action: A Computational Core

Lang, Jérôme; Lin, Fangzhen; Marquis, Pierre

Causal Theories of Action: A Computational Core

Jérôme Lang, Fangzhen Lin, Pierre Marquis

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1073-1077.

Abstract

We propose a framework for simple causal theories of action, and study the computational complexity in it of various reasoning tasks such as determinism, progression and regression under various assumptions. As it turned out, even the simplest one among them, one-step temporal projection with complete initial state, is intractable. We also briefly consider an extension of the framework to allow truly indeterministic actions, and find that this extension does not increase the complexity of any of the tasks considered here.

Jérôme Lang, Fangzhen Lin, and Pierre Marquis. 2003. Causal Theories of Action: A Computational Core. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 1073–1077. https://ijcai.org/proceedings/2003/153

@inproceedings{ijcai2003p153,
  title     = {Causal Theories of Action: A Computational Core},
  author    = {Lang, Jérôme and Lin, Fangzhen and Marquis, Pierre},
  booktitle = {Proceedings of the Eighteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-03}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Georg Gottlob},
  pages     = {1073--1077},
  year      = {2003},
  url       = {https://ijcai.org/proceedings/2003/153},
}

TY  - CPAPER
TI  - Causal Theories of Action: A Computational Core
AU  - Lang, Jérôme
AU  - Lin, Fangzhen
AU  - Marquis, Pierre
T2  - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2003
SP  - 1073
EP  - 1077
UR  - https://ijcai.org/proceedings/2003/153
ER  -