Reasoning about Evolving Nonmonotonic Knowledge Bases
  Recently, several approaches to updating knowledge bases modeled as extended
logic programs 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 extended logic programs and maintained by an
update policy. We first describe a formal model which captures various update
approaches, and we define a logical language for expressing properties of
evolving knowledge bases. We then investigate semantical and computational
properties of our framework, where we focus on properties of knowledge states
with respect to the canonical reasoning task of whether a given formula holds
on a given evolving knowledge base. In particular, we present finitary
characterizations of the evolution for certain classes of framework instances,
which can be exploited for obtaining decidability results. In more detail, we
characterize the complexity of reasoning for some meaningful classes of
evolving knowledge bases, ranging from polynomial to double exponential space
complexity.
