Abstract
Theoretical research has spent some years facing the problem of how to represent and provide semantics to updates of logic programs. This problem is relevant for addressing highly dynamic domains with logic programming techniques. Two of the most recent results are the definition of the refined stable and the well founded semantics for dynamic logic programs that extend stable model and well founded semantic to the dynamic case. We present here alternative, although equivalent, operational characterizations of these semantics by program transformations into normal logic programs. The transformations provide new insights on the computational complexity of these semantics, a way for better understanding the meaning of the update programs, and also a methodology for the implementation of these semantics. In this sense, the equivalence theorems in this paper constitute soundness an completeness results for the implementations of these semantics.
This work was supported by project POSI/40958/SRI/01, FLUX, and by the European Commission within the 6th Framework P. project Rewerse, no. 506779.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alferes, J.J., Banti, F., Brogi, A., Leite, J.A.: The refined extension principle for semantics of dynamic logic programming. Studia Logica 79(1) (2005)
Alferes, J.J., Leite, J.A., Pereira, L.M., Przymusinska, H., Przymusinski, T.C.: Dynamic updates of non-monotonic knowledge bases. The Journal of Logic Programming 45(1-3), 43–70 (2000); A preliminary version appeared in KR 1998
Alferes, J.J., Pereira, L.M., Przymusinska, H., Przymusinski, T.: LUPS: A language for updating logic programs. In: Artificial Intelligence, vol. 132(1&2) (2002)
Alferes, J.J., Banti, F., Brogi, A.: From logic programs updates to action description updates. In: CLIMA V (2004)
Banti, F., Alferes, J.J., Brogi, A.: The well founded semantics for dynamic logic programs. In: Lemaître, C. (ed.) Proceedings of the 9th Ibero-American Conference on Artificial Intelligence (IBERAMIA-9). LNCS (LNAI). Springer, Heidelberg (2004)
Buccafurri, F., Faber, W., Leone, N.: Disjunctive logic programs with inheritance. In: De Schreye, D. (ed.) Proceedings of the 1999 International Conference on Logic Programming (ICLP 1999). MIT Press, Cambridge (1999)
DLV. The DLV project - a disjunctive datalog system (and more) (2000), Available at http://www.dbai.tuwien.ac.at/proj/dlv/
Eiter, T., Fink, M., Sabbatini, G., Tompits, H.: On properties of update sequences based on causal rejection. Theory and Practice of Logic Programming (2002)
Van Gelder, A., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. Journal of the ACM 38(3), 620–650 (1991)
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R., Bowen, K.A. (eds.) 5th International Conference on Logic Programming, pp. 1070–1080. MIT Press, Cambridge (1988)
Homola, M.: Dynamic logic programming: Various semantics are equal on acyclic programs. In: Leite, J., Torroni, P. (eds.) 5th Int. Ws. on Computational Logic In Multi-Agent Systems (CLIMA V), Pre-Proceedings (2004) ISBN: 972-9119-37-6
Leite, J.A.: Logic program updates. Master’s thesis, Dept. de Informática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa (November 1997)
Leite, J.A.: Evolving Knowledge Bases. Frontiers in Artificial Intelligence and Applications, vol. 81. IOS Press, Amsterdam (2003)
Leite, J.A., Alferes, J.J., Pereira, L.M.: Minerva - a dynamic logic programming agent architecture. In: Meyer, J.-J.C., Tambe, M. (eds.) ATAL 2001. LNCS (LNAI), vol. 2333, pp. 141–157. Springer, Heidelberg (2002)
Leite, J.A., Pereira, L.M.: Iterated logic program updates. In: Jaffar, J. (ed.) Proceedings of the 1998 Joint International Conference and Symposium on Logic Programming (JICSLP 1998), pp. 265–278. MIT Press, Cambridge (1998)
Lifschitz, V., Woo, T.: Answer sets in general non-monotonic reasoning (preliminary report). In: Nebel, B., Rich, C., Swartout, W. (eds.) Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR 1992). Morgan-Kaufmann, San Francisco (1992)
Marek, W., Truszczynski, M.: Autoepistemic logics. Journal of the ACM 38(3), 588–619 (1991)
Sakama, C., Inoue, K.: Updating extended logic programs through abduction. In: Gelfond, M., Leone, N., Pfeifer, G. (eds.) LPNMR 1999. LNCS (LNAI), vol. 1730, pp. 147–161. Springer, Heidelberg (1999)
Sefranek, J.: A kripkean semantics for dynamic logic programming. In: Parigot, M., Voronkov, A. (eds.) LPAR 2000. LNCS (LNAI), vol. 1955, pp. 469–486. Springer, Heidelberg (2000)
SMODELS. The SMODELS system (2000), Available at http://www.tcs.hut.fi/Software/smodels/
Tarski, A.: A lattice–theoretic fixpoint theorem and its applications. Pacific Journal of Mathematics 5, 285–309 (1955)
XSB-Prolog. The XSB logic programming system, version 2.6 (2003), http://xsb.sourceforge.net
Zhang, Y., Foo, N.Y.: Updating logic programs. In: Prade, H. (ed.) Proceedings of the 13th European Conference on Artificial Intelligence, ECAI 1998 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Banti, F., Alferes, J.J., Brogi, A. (2005). Operational Semantics for DyLPs. In: Bento, C., Cardoso, A., Dias, G. (eds) Progress in Artificial Intelligence. EPIA 2005. Lecture Notes in Computer Science(), vol 3808. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11595014_5
Download citation
DOI: https://doi.org/10.1007/11595014_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30737-2
Online ISBN: 978-3-540-31646-6
eBook Packages: Computer ScienceComputer Science (R0)