Abstract
Recently, several approaches to updating knowledge bases modeled as extended logic programs (ELPs) have been introduced, ranging from basic methods to incorporate (sequences of) sets of rules into a logic program, to more elaborate methods which use an update policy for specifying how updates must be incorporated. In this paper, we introduce a framework for reasoning about evolving knowledge bases, which are represented as ELPs and maintained by an update policy. We describe a formal model which captures various update approaches, and define a logical language for expressing properties of evolving knowledge bases. We further investigate the semantical properties of knowledge states with respect to reasoning. In particular, we describe finitary characterizations of the evolution, and derive complexity results for our framework.
This work was supported by the Austrian Science Fund (FWF) under grants P13871-INF and N Z29-INF.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Alferes, J. Leite, L. Pereira, H. Przymusinska, and T. Przymusinski. Dynamic Updates of Non-Monotonic Knowledge Bases. J. Logic Programming, 45(1–3):43–70, 2000.
J. Alferes, L. Pereira, H. Przymusinska, and T. Przymusinski. LUPS-ALanguage for Updating Logic Programs. In Proc. LPNMR’99, LNAI 1730, pp. 162–176. Springer, 1999.
C. Baral, V. Kreinovich, and R. Trejo. Computational Complexity of Planning and Approximate Planning in the Presence of Incompleteness. AIJ, 122(1–2):241–267, 2000.
E. Clarke, O. Grumberg, and D. Peled. Model Checking. MIT Press, 1999.
E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and Expressive Power of Logic Programming. In Proc. 12th IEEE International Conference on Computational Complexity (CCC’ 97), pp. 82–101, 1997. Full paper ACM Computing Surveys, to appear.
T. Eiter, M. Fink, G. Sabbatini, and H. Tompits. Considerations on Updates of Logic Programs. In Proc. JELIA 2000, LNAI 1919, pp. 2–20. Springer, 2000.
T. Eiter, M. Fink, G. Sabbatini, and H. Tompits. On Properties of Update Sequences Based on Causal Rejection. Theory and Practice of Logic Programming, to appear.
T. Eiter, M. Fink, G. Sabbatini, and H. Tompits. A Framework for Declarative Update Specifications in Logic Programs. In Proc. IJCAI’01, pp. 649–654.
E. Emerson. Temporal and Modal Logics, Vol. B. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. Elsevier, 1990.
R. Fagin, J. Halpern, Y. Moses, and M. Vardi. Reasoning about Knowledge. MIT, 1995.
D. Gabbay and P. Smets, editors. Handbook on Defeasible Reasoning and Uncertainty Management Systems, Vol. III. Kluwer Academic, 1998.
M. Gelfond and V. Lifschitz. ClassicalNegation in Logic Programs and Disjunctive Databases. New Generation Computing, 9:365–385, 1991.
K. Inoue and C. Sakama. Updating Extended Logic Programs through Abduction. In Proc. LPNMR’99, LNAI 1730, pp. 147–161. Springer, 1999.
J. Lobo, R. Bhatia, and S. Naqvi. A Policy Description Language. In Proc. AAAI/IAAI’99, pp. 291–298. AAAI Press / MIT Press, 1999.
J. Lobo and T. Son. Reasoning about Policies Using Logic Programs. In Proc. AAAI 2001 Spring Symposium on Answer Set Programming, pp. 210–216, 2001.
V. Marek and M. Truszczyński. Revision Specifications by Means of Programs. In Proc. JELIA’94, LNAI 838, pp. 122–136. Springer, 1994.
V. Marek and M. Truszczyński. Revision Programming. TCS, 190(2):241–277, 1998.
M. Winslett. Updating Logical Databases. Cambridge University Press, 1990.
M. Wooldridge. Reasoning about Rational Agents. MIT Press, 2000.
M. Wooldridge. The Computational Complexity of Agent Design Problem. In Proc. International Conference on Multi-Agent Systems (ICMAS) 2000. IEEE Press, 2000.
Y. Zhang and N. Foo. Updating Logic Programs. In Proc. ECAI’98, pp. 403–407. 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eiter, T., Fink, M., Sabbatini, G., Tompits, H. (2001). Reasoning about Evolving Nonmonotonic Knowledge Bases. In: Nieuwenhuis, R., Voronkov, A. (eds) Logic for Programming, Artificial Intelligence, and Reasoning. LPAR 2001. Lecture Notes in Computer Science(), vol 2250. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45653-8_28
Download citation
DOI: https://doi.org/10.1007/3-540-45653-8_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42957-9
Online ISBN: 978-3-540-45653-7
eBook Packages: Springer Book Archive