On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols
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.
Cite
Text
Belle and Lakemeyer. "On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-131Markdown
[Belle and Lakemeyer. "On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/belle2011ijcai-progression/) doi:10.5591/978-1-57735-516-8/IJCAI11-131BibTeX
@inproceedings{belle2011ijcai-progression,
title = {{On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols}},
author = {Belle, Vaishak and Lakemeyer, Gerhard},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {744-749},
doi = {10.5591/978-1-57735-516-8/IJCAI11-131},
url = {https://mlanthology.org/ijcai/2011/belle2011ijcai-progression/}
}