Evolving logic programs

Abstract. Logic programming has often been considered less than ad-equate for modelling the dynamics of knowledge changing over time. In this paper we describe a simple though quite powerful approach to modelling the updates of knowledge bases expressed by generalized logic programs, by means of a new language, hereby christened EVOLP (after EVO lving Logic Programs). The approach was first sparked by a crit-ical analysis of previous efforts and results in this direction [1,2,7,11], and aims to provide a simpler, and at once more general, formulation of logic program updating, which runs closer to traditional logic program-ming (LP) doctrine. From the syntactical point of view, evolving pro-grams are just generalized logic programs (i.e. normal LPs plus default negation also in rule heads), extended with (possibly nested) assertions, whether in heads or bodies of rules. From the semantics viewpoint, a model-theoretic characterization is offered of the possible evolutions of such programs. These evolutions arise both from self (or internal) up-dating, and from external updating too, originating in the environment. This formulation sets evolving programs on a firm basis in which to ex-press, implement, and reason about dynamic knowledge bases, and opens up a number of interesting research topics that we brush on.