On the Compilability of Diagnosis, Planning, Reasoning about Actions, Belief Revision, etc.

Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98)

In this paper we investigate the usefulness of preprocessing part of the input of a given problem to improve the efficiency. We extend the results of [Cadoli et al. ISTCS, 1996] by giving sufficient conditions to prove the unfeasibility of reducing the on-line complexity via an off-line preprocessing. We analyze the problems of diagnosis, planning, reasoning about actions, and belief revision. We analyze other problems from various fields.

 @inproceedings{libe-98,
 title = {On the Compilability of Diagnosis, Planning, Reasoning about Actions,
 Belief Revision, etc.},
 year = {1998},
 author = {Liberatore, Paolo},
 booktitle = {Proceedings of the Sixth International Conference on Principles of
 Knowledge Representation and Reasoning (KR'98)},
 pages = {144-155},
 }