On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols

Vaishak Belle, Gerhard Lakemeyer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In a seminal paper, Lin and Reiter introduced the notion of progression of basic action theories. Unfortunately, progression is second-order in general. Recently, Liu and Lakemeyer improve on earlier results and show that for the local-effect and normal actions case, progression is computable but may lead to an exponential blow-up. Nevertheless, they show that for certain kinds of expressive first-order knowledge bases with disjunctive information, called proper+, it is efficient. However, answering queries about the resulting state is still undecidable. In this paper, we continue this line of research and extend proper+ KBs to include functions. We prove that their progression wrt local-effect, normal actions, and range restricted theories, is first-order definable and efficiently computable. We then provide a new logically sound and complete decision procedure for certain kinds of queries.
Original languageEnglish
Title of host publicationIJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011
PublisherIJCAI Inc
Pages744-749
Number of pages6
DOIs
Publication statusPublished - 2011

Cite this