### On the progression of situation calculus basic action theories: Resolving a 10-year-old conjectureOn the progression of situation calculus basic action theories: Resolving a 10-year-old conjecture

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 AAAIIn 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