First-Order Progression beyond Local-Effect and Normal Actions

Daxin Liu, Jens Claßen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


One of the fundamental problems in reasoning about action is progression, which is to update a knowledge base according to the effects of an action into another knowledge base that retains all proper information. The problem is notoriously challenging, as in general, it requires second-order logic. Efforts have been made to find fragments where progression is first-order definable. Liu and Lakemeyer showed that for actions that have only local effects, progression is always first-order definable. They also generalized the result to so-called normal actions, that allow for non-local effects, as long as the affected fluent predicates only depend on local-effect ones, under certain restrictions on the knowledge base. In addition, they showed that for so-called proper+ knowledge bases, progression for normal actions can be efficient under reasonable assumptions. In this paper, we consider a larger class of theories, called the acyclic ones, that strictly subsumes normal actions. In such theories, dependencies between non-local effect fluent predicates are allowed, as long as they do not contain any cycles. We prove progression to be equally first-order definable for this class. Furthermore, under similar but stronger assumptions than those made by Liu and Lakemeyer, we show that progression is efficient as well.
Original languageEnglish
Title of host publicationProceedings of the 33rd International Joint Conference on Artificial Intelligence
PublisherIJCAI Organization
Publication statusAccepted/In press - 15 May 2024
EventInternational Joint Conference on Artificial Intelligence - International Convention Center Jeju, Jeju Island, Korea, Republic of
Duration: 3 Aug 20249 Aug 2024
Conference number: 33


ConferenceInternational Joint Conference on Artificial Intelligence
LocationInternational Convention Center Jeju
Country/TerritoryKorea, Republic of
CityJeju Island
Internet address


  • Reasoning about actions and change, action languages

Cite this