A Tractable, Expressive, and Eventually Complete
First-Order Logic of Limited Belief
Abstract
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