Dynamic Complexity studies the maintainability of queries with logical formulas in a setting where the underlying structure or database changes over time. Most often, these formulas are from first-order logic, giving rise to the dynamic complexity class DynFO. This paper investigates extensions of DynFO in the spirit of parameterised algorithms. In this setting structures come with a parameter $k$ and the extensions allow additional "space" of size $f(k)$ (in the form of an additional structure of this size) or additional time $f(k)$ (in the form of iterations of formulas) or both. The resulting classes are compared with their non-dynamic counterparts and other classes. The main part of the paper explores the applicability of methods for parameterised algorithms to this setting through case studies for various well-known parameterised problems.

Abstract We present a probabilistic justification logic, $\mathsf{PPJ}$, as a framework for uncertain reasoning about rational belief, degrees of belief and justifications. We establish soundness and strong completeness for $\mathsf{PPJ}$ with respect to the class of so-called measurable Kripke-like models and show that the satisfiability problem is decidable. We discuss how $\mathsf{PPJ}$ provides insight into the well-known lottery paradox.