A Tractability Result for Reasoning with Incomplete First-Order Knowledge Bases
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 83-87.
Abstract
In previous work, Levesque proposed an extension to classical databases that would allow for a certain form of incomplete first-order knowledge. Since this extension was sufficient to make full logical deduction undecidable, he also proposed an alternative reasoning scheme with desirable logical properties. He also claimed (without proof) that this reasoning could be implemented efficiently using database techniques such as projections and joins. In this paper, we substantiate this claim and show how to adapt a bottom-up database query evaluation algorithm for this purpose, thus obtaining a tractability result comparable to those that exist for databases.
@inproceedings{ijcai2003p12,
title = {A Tractability Result for Reasoning with Incomplete First-Order Knowledge Bases},
author = {Liu, Yongmei and Levesque, Hector J.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {83--87},
year = {2003},
url = {https://ijcai.org/proceedings/2003/12},
}
TY - CPAPER TI - A Tractability Result for Reasoning with Incomplete First-Order Knowledge Bases AU - Liu, Yongmei AU - Levesque, Hector J. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 83 EP - 87 UR - https://ijcai.org/proceedings/2003/12 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
