Thumbnail
Access Restriction
Open

Author Vassos, Stavros ♦ Levesque, Hector J.
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword First-order Definable Progression ♦ Strong Negative Result ♦ Significant Result ♦ Action Theory ♦ First-order Logic ♦ Initial Knowl-edge Base ♦ Alter-native Definition ♦ 10-year-old Conjecture ♦ Model-theoretic Definition ♦ Second-order Axiom ♦ Basic Action Theory ♦ Seminal Paper ♦ Large Class ♦ Alternative Definition ♦ Progressed Theory ♦ Certain Kind ♦ Preferred Option ♦ Reiter Conjecture ♦ Situation Calculus Basic Action Theory
Description In Proc. of AAAI
In a seminal paper, Lin and Reiter introduced a model-theoretic definition for the progression of the initial knowl-edge base of a basic action theory. This definition comes with a strong negative result, namely that for certain kinds of action theories, first-order logic is not expressive enough to correctly characterize this form of progression, and second-order axioms are necessary. However, Lin and Reiter also considered an alternative definition for progression which is always first-order definable. They conjectured that this alter-native definition is incorrect in the sense that the progressed theory is too weak and may sometimes lose information. This conjecture, and the status of first-order definable progression, has remained open since then. In this paper we present two significant results about this alternative definition of progres-sion. First, we prove the Lin and Reiter conjecture by pre-senting a case where the progressed theory indeed does lose information. Second, we prove that the alternative definition is nonetheless correct for reasoning about a large class of sen-tences, including some that quantify over situations. In this case the alternative definition is a preferred option due to its simplicity and the fact that it is always first-order.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article