On Progression and Query Evaluation in First-Order Knowledge Bases with Function Symbols
By Vaishak Belle, Gerhard Lakemeyer. 2011
11 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
Citations in the corpus
- Logic meets Probability: Towards Explainable AI Systems for Uncertain Worlds (2017, background): “Interestingly, tractability can often be decoupled in terms of the expressiveness of the knowledge base and that of the action model [Belle and Lakemeyer, 2011].”
- Open-Universe Weighted Model Counting (2017, result): “From the representation side, our language and KB syntax is based on modal logic with rigid designators (Levesque and Lakemeyer 2001; Lakemeyer and Levesque 2002; Belle and Lakemeyer 2011).”