ABSTRACT. Structural recursion is arguably the most important definitional principle in theoretical computer science. Traditionally, one defines (or programs) functions over an inductive datatype by structural recursion over the datatype's constructors. This amounts to writing clauses indicating how the to-be-defined function is supposed to interact with the constructors. For example, to define the length of a list we can write: length Nil = 0, and length (Cons x xs) = length xs + 1. However, this works out of the box only if the datatype is freely generated by the constructors, in that the constructors are injective and non-overlapping. On the other hand, for non-free datatypes such as finite sets, bags, and terms with bindings under the nominal representation, mathematicians and computer scientists have devised mechanisms for making structural recursion work with the help of verifying certain conditions.

In this talk, I will distill the ideas underlying recursion on non-free datatypes into the notion of epi-recursor. This is a simple piece of categorical logic that separates the constructor layer from a layer that "sits on top" of it, consisting of operators and properties that further support recursion. I will show how this abstract view can shed light on the relative expressiveness of different recursors. Finally, I will look at the dual problem of supporting corecursion via epi-corecursion, and its applications to defining functions that manipulate infinitary structures with bindings such as Boehm trees.

ABSTRACT. This paper is engaged with realizability in the realm of abstract argumentation. In particular, we deal with naive labellings forming the basis for a well-established family of semantics, namely the naivity-based semantics. Consequently, characterizing this semantics is a crucial step towards delineating further naivety-based semantics such as stable and stage semantics. We provide easily verifiable criteria deciding whether a certain set of labellings can be the naive outcome of a Dungean framework. Apart from this we also present a standard construction in the affirmative case. This means, constructing a witnessing framework for a realizable set of naive labelling is possible paving the way for applications. Finally, we offer insights into representational freedom and prove a kernel-based characterization for strong equivalence, which substantially differ from its extension-based counterpart.

ABSTRACT. This paper investigates variable forgetting and marginalization in propositional logic. We show that for finite signatures and infinite signatures, variable forgetting and marginalization are corresponding operations, i.e., they yield semantically equivalent outputs for respective complementary inputs. This observation holds for formulas and also for sets of formulas. For formulas, both operations, variable forgetting and marginalization, are shown to be compatible with disjunctions, but not with conjunction, implication and negation. For general sets of formulas, a consequence is that the element-wise application of these operations to a set of formulas and the application to a formula equivalent to this set are not equivalent in general. However, for every deductively closed set X, we show that the element-wise application of variable forgetting or marginalization, respectively, and the application to any formula equivalent to X are equivalent. This latter observation is important because deductively closed sets play an important role in many areas, e.g., in logic-based approaches to knowledge representation and databases.

ABSTRACT. Epistemic logic (EL) successfully models epistemic and doxastic attitudes of agents and groups in multi-agent systems, including distributed systems, via relational structures called Kripke models. Dynamic Epistemic Logic (DEL) adds communication in the form of model transforming updates. Private communication is key in distributed systems as processes exchanging (potentially corrupted) information about their private local state should not be detectable by any other processes. This focus on privacy clashes with the fact that updates are applied to the whole Kripke model, which is usually commonly known by all agents, potentially leading to information leakage. To avoid information leakage and to minimize the corruption of local states resulting from fault information, we introduce a special stratified structure for Kripke models, using a privatization operation that explicitly breaks the common knowledge of the model. To represent agent-to-agent communication we introduce a novel leakage-free update mechanism for solving the consistent update synthesis task: design an update that makes a given goal formula true while maintaining the consistency of agents’ beliefs, if possible.

ABSTRACT. Ranking functions, also called ordinal conditional functions (OCF), provide a semantics for conditionals by assigning a degree of implausibility to the underlying possible worlds. The entailment relation c-inference takes all c-representations, which are special ranking functions, into account, and exhibits excellent properties put forward for nonmonotonic reasoning. All previous implementations of c-inference, however, are severely limited by the requirement of having to show the unsolvability of a complex constraint satisfaction problem (CSP) whose size grows exponentially with the number of signature elements. In this paper, we present an approach for reducing the size of the CSP underlying c-inference significantly by using partial maximum satisfiability problems (PMaxSAT) and the power of current PMaxSAT solvers. In particular, we introduce the dual notion of minimum satisfiability problems for simplifying the minimum expressions in the CSP. We prove the soundness of our CSP optimization and develop an implementation for it. An evaluation demonstrates that it outperforms all previous implementations and dramatically scales up c-inference to a new dimension.

ABSTRACT. We investigate the generalization of causal models to the case of indeterministic causal laws that was suggested in Halpern (2000). We give an overview of what differences in modeling are enforced by this more general perspective, and propose an implementation of generalized models in the style of the causal team semantics of Barbero & Sandu (2020). In these models, the laws are not represented by functions (as in the deterministic case), but more generally by relations.

We analyze significant differences in the axiomatization of interventionist counterfactuals in the indeterministic vs. the deterministic case, and provide strongly complete axiomatizations over the full class of indeterministic models and over its recursive subclass.

ABSTRACT. We consider probabilistic independence and unary variants of marginal identity and marginal distribution equivalence over finite probability distributions. Two variables x and y satisfy a unary marginal identity when they are identically distributed. If the multisets of the marginal probabilities of all possible values for variables x and y are equal, the variables satisfy a unary marginal distribution equivalence. This paper offers a sound and complete finite axiomatization and a polynomial-time algorithm for the implication problem for probabilistic independence, unary marginal identity, and unary marginal distribution equivalence.