On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols. Belle, V. & Lakemeyer, G. In Twenty-second International Joint Conference on Artificial Intelligence (IJCAI-11) , Barcelona, Spain, 2011. AAAI Press, AAAI Press. Paper abstract bibtex 12 downloads 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.
@inproceedings {KBSG_219,
title = {On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols},
booktitle = {Twenty-second International Joint Conference on Artificial Intelligence (IJCAI-11) },
year = {2011},
publisher = {AAAI Press},
organization = {AAAI Press},
address = {Barcelona, Spain},
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. },
url_Paper = {https://kbsg.rwth-aachen.de/sites/kbsg/files/ijcai11.pdf},
author = {Belle, Vaishak and Lakemeyer, Gerhard}
}
Downloads: 12
{"_id":{"_str":"534212c91e2ff87b0700001d"},"__v":11,"authorIDs":["54575ce32abc8e9f37000307","545792562abc8e9f37000523","5da9a083452932db010000be","5e3902b8dc5b8ade010000a6","5e60e839839e59df010000ed","vsrgwisAvsx5co5Zd"],"author_short":["Belle, V.","Lakemeyer, G."],"bibbaseid":"belle-lakemeyer-onprogressionandqueryevaluationinfirstorderknowledgebaseswithfunctionsymbols-2011","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols","booktitle":"Twenty-second International Joint Conference on Artificial Intelligence (IJCAI-11) ","year":"2011","publisher":"AAAI Press","organization":"AAAI Press","address":"Barcelona, Spain","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. ","url_paper":"https://kbsg.rwth-aachen.de/sites/kbsg/files/ijcai11.pdf","author":[{"propositions":[],"lastnames":["Belle"],"firstnames":["Vaishak"],"suffixes":[]},{"propositions":[],"lastnames":["Lakemeyer"],"firstnames":["Gerhard"],"suffixes":[]}],"bibtex":"@inproceedings {KBSG_219,\n title = {On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols},\n booktitle = {Twenty-second International Joint Conference on Artificial Intelligence (IJCAI-11) },\n year = {2011},\n publisher = {AAAI Press},\n organization = {AAAI Press},\n address = {Barcelona, Spain},\n 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. },\n url_Paper = {https://kbsg.rwth-aachen.de/sites/kbsg/files/ijcai11.pdf},\n author = {Belle, Vaishak and Lakemeyer, Gerhard}\n}\n","author_short":["Belle, V.","Lakemeyer, G."],"key":"KBSG_219","id":"KBSG_219","bibbaseid":"belle-lakemeyer-onprogressionandqueryevaluationinfirstorderknowledgebaseswithfunctionsymbols-2011","role":"author","urls":{" paper":"https://kbsg.rwth-aachen.de/sites/kbsg/files/ijcai11.pdf"},"metadata":{"authorlinks":{"belle, v":"https://bibbase.org/show?msg=embed&bib=https://dblp.org/pid/52/570.bib"}},"downloads":12},"bibtype":"inproceedings","biburl":"https://kbsg.rwth-aachen.de/files/kbsgweb.bib","downloads":12,"keywords":[],"search_terms":["progression","query","evaluation","first","order","knowledge","bases","function","symbols","belle","lakemeyer"],"title":"On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols","year":2011,"dataSources":["2LLKDfkxMDdABm58M","r9FAaXnZMktuR9SCv","ayruv4JDJNMLz7ieC","vAo9zFmkx4MpPsgha","dqRQPSg6Hy3ZXQg7z"]}