@InProceedings{vassos08conjecture,
  Title                    = {On the Progression of Situation Calculus Basic Action Theories:
 Resolving a 10-year-old Conjecture},
  Author                   = {Vassos, Stavros and Levesque, Hector},
  Booktitle                = {Proceedings of the Twenty-Third AAAI Conference on Artificial
 Intelligence (AAAI-08)},
  Year                     = {2008},

  Address                  = {Chicago, Illinois, USA},
  Month                    = {July 13--17},
  Pages                    = {1004-1009},

  Abstract                 = {In a seminal paper, Lin and Reiter introduced a
model-theoretic definition for the progression of the initial
knowledge 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 alternative
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 progression. First, we prove
the Lin and Reiter conjecture by presenting 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 sentences, 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.},
  Areas                    = {Cognitive Robotics},
  Keyword                  = {progression, reasoning about action, situation calculus, cognitive robotics},
  Timestamp                = {2018.09.23},
  Url                      = {vassos-levesque08conjecture.pdf}
}

{"_id":"Sx6pgLDLAZjb3wejd","bibbaseid":"vassos-levesque-ontheprogressionofsituationcalculusbasicactiontheoriesresolvinga10yearoldconjecture-2008","authorIDs":[],"author_short":["Vassos, S.","Levesque, H."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture","author":[{"propositions":[],"lastnames":["Vassos"],"firstnames":["Stavros"],"suffixes":[]},{"propositions":[],"lastnames":["Levesque"],"firstnames":["Hector"],"suffixes":[]}],"booktitle":"Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-08)","year":"2008","address":"Chicago, Illinois, USA","month":"July 13–17","pages":"1004-1009","abstract":"In a seminal paper, Lin and Reiter introduced a model-theoretic definition for the progression of the initial knowledge 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 alternative 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 progression. First, we prove the Lin and Reiter conjecture by presenting 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 sentences, 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.","areas":"Cognitive Robotics","keyword":["progression"," reasoning about action"," situation calculus"," cognitive robotics"],"timestamp":"2018.09.23","url":"vassos-levesque08conjecture.pdf","bibtex":"@InProceedings{vassos08conjecture,\n Title = {On the Progression of Situation Calculus Basic Action Theories:\n Resolving a 10-year-old Conjecture},\n Author = {Vassos, Stavros and Levesque, Hector},\n Booktitle = {Proceedings of the Twenty-Third AAAI Conference on Artificial\n Intelligence (AAAI-08)},\n Year = {2008},\n\n Address = {Chicago, Illinois, USA},\n Month = {July 13--17},\n Pages = {1004-1009},\n\n Abstract = {In a seminal paper, Lin and Reiter introduced a\nmodel-theoretic definition for the progression of the initial\nknowledge base of a basic action theory. This definition comes\nwith a strong negative result, namely that for certain kinds of\naction theories, first-order logic is not expressive enough to\ncorrectly characterize this form of progression, and second-order\naxioms are necessary. However, Lin and Reiter also considered an\nalternative definition for progression which is always\nfirst-order definable. They conjectured that this alternative\ndefinition is incorrect in the sense that the progressed theory\nis too weak and may sometimes lose information. This conjecture,\nand the status of first-order definable progression, has remained\nopen since then. In this paper we present two significant results\nabout this alternative definition of progression. First, we prove\nthe Lin and Reiter conjecture by presenting a case where the\nprogressed theory indeed does lose information. Second, we prove\nthat the alternative definition is nonetheless correct for\nreasoning about a large class of sentences, including some that\nquantify over situations. In this case the alternative definition\nis a preferred option due to its simplicity and the fact that it\nis always first-order.},\n Areas = {Cognitive Robotics},\n Keyword = {progression, reasoning about action, situation calculus, cognitive robotics},\n Timestamp = {2018.09.23},\n Url = {vassos-levesque08conjecture.pdf}\n}\n\n","author_short":["Vassos, S.","Levesque, H."],"key":"vassos08conjecture","id":"vassos08conjecture","bibbaseid":"vassos-levesque-ontheprogressionofsituationcalculusbasicactiontheoriesresolvinga10yearoldconjecture-2008","role":"author","urls":{"Paper":"http://www.cs.toronto.edu/kr/publications/vassos-levesque08conjecture.pdf"},"metadata":{"authorlinks":{}},"downloads":1,"html":""},"bibtype":"inproceedings","biburl":"http://www.cs.toronto.edu/kr/publications/list.bib","creationDate":"2021-03-03T03:35:26.044Z","downloads":1,"keywords":["progression"," reasoning about action"," situation calculus"," cognitive robotics"],"search_terms":["progression","situation","calculus","basic","action","theories","resolving","year","old","conjecture","vassos","levesque"],"title":"On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture","year":2008,"dataSources":["2LLKDfkxMDdABm58M","optQ3PYGE2PxhriFJ","vAo9zFmkx4MpPsgha"]}