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

Belle, Vaishak; Lakemeyer, Gerhard

doi:10.5591/978-1-57735-516-8/IJCAI11-131

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

Vaishak Belle, Gerhard Lakemeyer

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 744-748.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-131

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+ 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.

Vaishak Belle, and Gerhard Lakemeyer. 2011. On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 744–748. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-131

@inproceedings{ijcai2011p131,
  title     = {On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols},
  author    = {Belle, Vaishak and Lakemeyer, Gerhard},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {744--748},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-131},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-131},
}

TY  - CPAPER
TI  - On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols
AU  - Belle, Vaishak
AU  - Lakemeyer, Gerhard
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 744
EP  - 748
DO  - 10.5591/978-1-57735-516-8/IJCAI11-131
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-131
ER  -