A Tractable, Expressive, and Eventually Complete First-Order Logic of Limited Belief

A Tractable, Expressive, and Eventually Complete First-Order Logic of Limited Belief

Gerhard Lakemeyer, Hector J. Levesque

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1764-1771. https://doi.org/10.24963/ijcai.2019/244

In knowledge representation, obtaining a notion of belief which is tractable, expressive, and eventually complete has been a somewhat elusive goal. Expressivity here means that an agent should be able to hold arbitrary beliefs in a very expressive language like that of first-order logic, but without being required to perform full logical reasoning on those beliefs. Eventual completeness means that any logical consequence of what is believed will eventually come to be believed, given enough reasoning effort. Tractability in a first-order setting has been a research topic for many years, but in most cases limitations were needed on the form of what was believed, and eventual completeness was so far restricted to the propositional case. In this paper, we propose a novel logic of limited belief, which has all three desired properties.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Logics for Knowledge Representation
Knowledge Representation and Reasoning: Reasoning about Knowlege and Belief