Fundamental to reasoning about actions and beliefs is the projection problem: to decide what is believed after a sequence of actions is performed. Progression is one widely applied technique to solve this problem. In this paper we propose a novel framework for computing progression in the epistemic situation calculus. In particular, we model an agent's preferential belief structure using conditional statements and provide a technique for updating these conditional statements as actions are performed and sensing information is received. Moreover, we show, by using the concepts of natural revision and only-believing, that the progression of a conditional knowledge base can be represented by only-believing the revised set of conditional statements. These results lay the foundations for feasible belief progression due to the unique-model property of only-believing.

Parameterized complexity is a well recognized vehicle for understanding the multitude of complexity AI problems typically exhibit. However, the prominent problem of belief revision has not undergone a systematic investigation in this direction yet. This is somewhat surprising, since by its very nature of involving a knowledge base and a revision formula, this problem provides a perfect playground for investigating novel parameters. Among our results on the parameterized complexity of revision is thus a versatile fpt algorithm which is based on the parameter of the number of atoms shared by the knowledge base and the revision formula. Towards identifying the frontier between parameterized tractability and intractability, we also give hardness results for classes such as co-W[1], para-Theta 2 P and FPT NP[f(k)]

The AGM paradigm of belief change studies the dynamics of belief states in light of new information. Finding, or even approximating, dependent or relevant beliefs to a change is valuable because, for example, it can narrow the set of beliefs considered during belief change operations. Gärdenfors' preservation criterion (GPC) suggests that formulas independent of a belief change should remain intact. GPC allows to build dependence relations that are theoretically linked with belief change. Such dependence relations can in turn be used as a theoretical benchmark against which to evaluate other approximate dependence or relevance relations. There are already some studies, based on GPC, on the parallelism between belief change and dependence. One study offers a dependence relation parallel to AGM contraction for belief sets. Another study links base dependence relation to a more general belief base contraction, saturated kernel contraction. Here we offer yet a more general parallelism between kernel contraction and base dependence. At this level of generalization, different types of base dependence emerge. We prove that this differentiation of base dependence types is a result of possible redundancy in the base. This provides a theoretical means to distinguish between redundant and informative parts of a belief base.

Belief revision is concerned with incorporating new information into a pre-existing set of beliefs. When the new information comes from another agent, we must first determine if that agent should be trusted. In this paper, we define trust as a pre-processing step before revision. We emphasize that trust in an agent is often restricted to a particular domain of expertise. We demonstrate that this form of trust can be captured by associating a state partition with each agent, then relativizing all reports to this partition before revising.  We position the resulting family of trust-sensitive revision operators within the class of selective revision operators of Ferme and Hansson, and we examine its properties. In particular, we show how trust-sensitive revision is manipulable, in the sense that agents can sometimes have incentive to pass on misleading information.  When multiple reporting agents are involved, we use a distance function over states to represent differing degrees of trust; this ensures that the most trusted reports will be believed.

Belief merging is a central operation within the field of belief change and addresses the problem of combining multiple, possibly mutually inconsistent knowledge bases into a single, consistent one. A current research trend in belief change is concerned with tailored representation theorems for fragments of logic, in particular Horn logic. Hereby, the goal is to guarantee that the result of the change operations stays within the fragment under consideration. While several such results have been obtained for Horn revision and Horn contraction, merging of Horn theories has been neglected so far. In this paper, we provide a novel representation theorem for Horn merging by strengthening the standard merging postulates. Moreover, we present a concrete Horn merging operator satisfying all postulates.

In a seminal paper, Lin and Reiter introduced the notion of progression for basic action theories in the situation calculus. Recently, Fang and Liu extended the situation calculus to account for multi-agent knowledge and belief change. In this paper, based on their framework, we investigate progression of both belief and knowledge in the single-agent propositional case. We first present a model-theoretic definition of progression of knowledge and belief. We show that for propositional actions, i.e., actions whose precondition axioms and successor state axioms are propositional formulas, progression of knowledge and belief reduces to forgetting in the logic of knowledge and belief, which we show is closed under forgetting. Consequently, we are able to show that for propositional actions, progression of knowledge and belief is always definable in the logic of knowledge and belief.

Argumentation is an inherently dynamic process. Given that argumentation can be viewed as a process as well Consequently, recent years have witnessed tremendous as a product, recent years have seen an increasing number of research efforts towards an understanding of studies on different problems in the dynamics of argumentation how the seminal AGM theory of belief change can frameworks [Baumann, 2012; Bisquert et al., 2011; 2013; be applied to argumentation, in particular for Dung's Boella et al., 2009; Booth et al., 2013; Cayrol et al., 2010; abstract argumentation frameworks (AFs). However, Doutre et al., 2014; Kontarinis et al., 2013; Krümpelmann et none of the attempts has yet succeeded in handling al., 2012; Nouioua and Würbel, 2014; Sakama, 2014]. The the natural situation where the revision of an AF is problem we tackle here is how to revise an AF when some new guaranteed to be representable by an AF as well.

When a belief state is represented as a probability function P, the resulting belief state of the contraction of a sentence (belief) from the original belief state P can be given by the probabilistic version of the Harper Identity. Specifically, the result of contracting P by a sentence h is taken to be the mixture of two states: the original state P, and the resultant state P* ~h of revising P by the negation of h. What proportion of P and P* ~h should be used in this mixture remains an open issue and is largely ignored in literature. In this paper, we first classify different belief states by their stability, and then exploit the quantitative nature of probabilities and combine it with the basic ideas of argumentation theory to determine  the mixture proportions. We, therefore, propose a novel approach to probabilistic belief contraction using argumentation.

Stream reasoning is the task of continuously deriving conclusions on streaming data. To get results instantly one evaluates a query repeatedly on recent data chunks selected by window operators. However, simply recomputing results from scratch is impractical for rule-based reasoning with semantics similar to Answer Set Programming, due to the trade-off between complexity and data throughput. To address this problem, we present a method to efficiently update models of a rule set. In particular, we show how an answer stream (model) of a LARS program can be incrementally adjusted to new or outdated input by extending truth maintenance techniques. We obtain in this way a means towards practical rule-based stream reasoning with nonmonotonic negation, various window operators and different forms of temporal reference.

In this paper we combine two of the most important areas of knowledge representation, namely belief revision and (abstract) argumentation. More precisely, we show how AGM-style expansion and revision operators can be defined for Dung's abstract argumentation frameworks (AFs). Our approach is based on a reformulation of the original AGM postulates for revision in terms of monotonic consequence relations for AFs. The latter are defined via a new family of logics, called Dung logics, which satisfy the important property that ordinary equivalence in these logics coincides with strong equivalence for the respective argumentation semantics. Based on these logics we define expansion as usual via intersection of models. We show the existence of such operators. This is far from trivial and requires to study realizability in the context of Dung logics. We then study revision operators. We show why standard approaches based on a distance measure on models do not work for AFs and present an operator satisfying all postulates for a specific Dung logic.