Ladner’s theorem states that if P ≠ NP, then there are problems in NP that are neither in P nor NP-complete. Csp(Γ) is a class of problems containing many well-studied combinatorial problems in NP. Csp(Γ) problems are of the form: given a set of variables constrained by a set of constraints from the set of allowed constraints Γ, is there an assignment to the variables satisfying all constraints? A famous, and in the light of Ladner’s theorem, surprising conjecture states that there is a complexity dichotomy for Csp(Γ); that is, for any fixed finite Γ, the Csp(Γ) problem is either in P or NP-complete. In this thesis we focus on problems expressible in the Csp(Γ) framework with different computational goals, such as: counting the number of solutions, deciding whether two sets of constraints have the same set of solutions, deciding whether all minimal solutions of a set of constraints satisfies an additional constraint etc. By doing so, we capture a host of problems ranging from fundamental problems in nonmonotonic logics, such as abduction and circumscription, to problems regarding the equivalence of systems of linear equations. For several of these classes of problem, we are able to give complete complexity classifications and rule out the possibility of problems of intermediate complexity. For example, we prove that the inference problem in propositional variable circumscription, parameterized by the set of allowed constraints Γ, is either in P, coNP-complete, or ΠP/2-complete. As a by-product of these classifications, new tractable cases and hardness results for well-studied problems are discovered. The techniques we use to obtain these complexity classifications are to a large extent based on connections between algebraic clone theory and the complexity of Csp(Γ). We are able to extend these powerful algebraic techniques to several of the problems studied in this thesis. Hence, this thesis also contributes to the understanding of when these algebraic techniques are applicable and not.

The field of artificial intelligence, research on knowledge representation and reasoning has originated a large variety of formats, languages, and formalisms. Over the decades many different tools emerged to use these underlying concepts. Each one has been designed with some specific application in mind and are even used nowadays, where the internet is seen as a service to be sufficient for the age of Industry 4.0 and the Internet of Things. In that vision of a connected world, with these many different formalisms and systems, a formal way to uniformly exchange information, such as knowledge and belief is imperative. That alone is not enough, because even more systems get integrated into the online world and nowadays we are confronted with a huge amount of continuously flowing data. Therefore a solution is needed to both, allowing the integration of information and dynamic reaction to the data which is provided in such continuous data-flow environments. This work aims to present a unique and novel pair of formalisms to tackle these two important needs by proposing an abstract and general solution. We introduce and discuss reactive Multi-Context Systems (rMCS), which allow one to utilise different knowledge representation formalisms, so-called contexts which are represented as an abstract logic framework, and exchange their beliefs through bridge rules with other contexts. These multiple contexts need to mutually agree on a common set of beliefs, an equilibrium of belief sets. While different Multi-Context Systems already exist, they are only solving this agreement problem once and are neither considering external data streams, nor are they reasoning continuously over time. rMCS will do this by adding means of reacting to input streams and allowing the bridge rules to reason with this new information. In addition we propose two different kind of bridge rules, declarative ones to find a mutual agreement and operational ones for adapting the current knowledge for future computations. The second framework is more abstract and allows computations to happen in an asynchronous way. These asynchronous Multi-Context Systems are aimed at modelling and describing communication between contexts, with different levels of self-management and centralised management of communication and computation. In this thesis rMCS will be analysed with respect to usability, consistency management, and computational complexity, while we will show how asynchronous Multi-Context Systems can be used to capture the asynchronous ideas and how to model an rMCS with it. Finally we will show how rMCSs are positioned in the current world of stream reasoning and that it can capture currently used technologies and therefore allows one to seamlessly connect different systems of these kinds with each other. Further on this also shows that rMCSs are expressive enough to simulate the mechanics used by these systems to compute the corresponding results on its own as an alternative to already existing ones. For asynchronous Multi-Context Systems, we will discuss how to use them and that they are a very versatile tool to describe communication and asynchronous computation.

The ability to change one's beliefs in a rational manner is one of many facets of the abilities of an intelligent agent. Central to any investigation of belief change is the notion of an epistemic state. This dissertation is mainly concerned with three issues involving epistemic states: 1. How should an epistemic state be represented? 2. How does an agent use an epistemic state to perform belief change? 3. How does an agent arrive at a particular epistemic state? With regard to the first question, note that there are many different methods for constructing belief change operations. We argue that semantic constructions involving ordered pairs, each consisting of a set of beliefs and an ordering on the set of "possible worlds" (or equivalently, on the set of basic independent bits of information) are, in an important sense, more fundamental. Our answer to the second question provides indirect support for the use of semantic structures. We show how well-known belief change operations and related structures can be modelled semantically. Furthermore, we introduce new forms of belief change related operations and structures which are all defined, and motivated, in terms of such semantic representational formalisms. These include a framework for unifying belief revision and nonmonotonic reasoning, new versions of entrenchment orderings on beliefs, novel approaches to withdrawal operations, and an expanded view of iterated belief change. The third question is. one which has not received much attention in the belief change literature. We propose to extract extra-logical information from the formal representation of an agent's set of beliefs, which can then be used in the construction of epistemic state. his proposal is just a first approximation, although it seems to have the potential for developing into a full-fledged theory. / Computing / D.Phil.(Computer Science)

The ability to change one's beliefs in a rational manner is one of many facets of the abilities of an intelligent agent. Central to any investigation of belief change is the notion of an epistemic state. This dissertation is mainly concerned with three issues involving epistemic states: 1. How should an epistemic state be represented? 2. How does an agent use an epistemic state to perform belief change? 3. How does an agent arrive at a particular epistemic state? With regard to the first question, note that there are many different methods for constructing belief change operations. We argue that semantic constructions involving ordered pairs, each consisting of a set of beliefs and an ordering on the set of "possible worlds" (or equivalently, on the set of basic independent bits of information) are, in an important sense, more fundamental. Our answer to the second question provides indirect support for the use of semantic structures. We show how well-known belief change operations and related structures can be modelled semantically. Furthermore, we introduce new forms of belief change related operations and structures which are all defined, and motivated, in terms of such semantic representational formalisms. These include a framework for unifying belief revision and nonmonotonic reasoning, new versions of entrenchment orderings on beliefs, novel approaches to withdrawal operations, and an expanded view of iterated belief change. The third question is. one which has not received much attention in the belief change literature. We propose to extract extra-logical information from the formal representation of an agent's set of beliefs, which can then be used in the construction of epistemic state. his proposal is just a first approximation, although it seems to have the potential for developing into a full-fledged theory. / Computing / D.Phil.(Computer Science)

The study of nonmonotonic logics is one mayor field of Artificial Intelligence (AI). The reason why such kind of formalisms are so attractive to model human reasoning is that they allow to withdraw former conclusion. At the end of the 1980s the novel idea of using argumentation to model nonmonotonic reasoning emerged in AI. Nowadays argumentation theory is a vibrant research area in AI, covering aspects of knowledge representation, multi-agent systems, and also philosophical questions. Phan Minh Dung’s abstract argumentation frameworks (AFs) play a dominant role in the field of argumentation. In AFs arguments and attacks between them are treated as primitives, i.e. the internal structure of arguments is not considered. The major focus is on resolving conflicts. To this end a variety of semantics have been defined, each of them specifying acceptable sets of arguments, so-called extensions, in a particular way. Although, Dung-style AFs are among the simplest argumentation systems one can think of, this approach is still powerful. It can be seen as a general theory capturing several nonmonotonic formalisms as well as a tool for solving well-known problems as the stable-marriage problem. This thesis is mainly concerned with the investigation of metalogical properties of Dung’s abstract theory. In particular, we provide cardinality, monotonicity and splitting results as well as characterization theorems for equivalence notions. The established results have theoretical and practical gains. On the one hand, they yield deeper theoretical insights into how this nonmonotonic theory works, and on the other the obtained results can be used to refine existing algorithms or even give rise to new computational procedures. A further main part is the study of problems regarding dynamic aspects of abstract argumentation. Most noteworthy we solve the so-called enforcing and the more general minimal change problem for a huge number of semantics.

Nuel Belnap schlug 1977 eine vierwertige Logik vor, die -- im Gegensatz zur klassischen Logik -- die Faehigkeit haben sollte, sowohl mit widerspruechlicher als auch mit fehlender Information umzugehen. Diese Logik hat jedoch den Nachteil, dass sie Saetze der Form 'wenn ..., dann ...' nicht ausdruecken kann. Ausgehend von dieser Beobachtung analysieren wir die beiden nichtklassischen Aspekte, Widerspruechlichkeit und fehlende Information, indem wir eine dreiwertige Logik entwickeln, die mit widerspruechlicher Information umgehen kann und eine Modallogik, die mit fehlender Information umgehen kann. Beide Logiken sind nicht monoton. Wir untersuchen Eigenschaften, wie z.B. Kompaktheit, Entscheidbarkeit, Deduktionstheoreme und Berechnungkomplexitaet dieser Logiken. Es stellt sich heraus, dass die dreiwertige Logik, nicht kompakt und ihre Folgerungsmenge im Allgemeinen nicht rekursiv aufzaehlbar ist. Beschraenkt man sich hingegen auf endliche Formelmengen, so ist die Folgerungsmenge rekursiv entscheidbar, liegt in der Klasse $\Sigma_2^P$ der polynomiellen Zeithierarchie und ist DIFFP-schwer. Wir geben ein auf semantischen Tableaux basierendes, korrektes und vollstaendiges Berechnungsverfahren fuer endliche Praemissenmengen an. Darueberhinaus untersuchen wir Abschwaechungen der Kompaktheitseigenschaft. Die nichtmonotone auf S5-Modellen basierende Modallogik stellt sich als nicht minder komplex heraus. Auch hier untersuchen wir eine sinnvolle Abschwaechung der Kompaktheitseigenschaft. Desweiteren studieren wir den Zusammenhang zu anderen nichtmonotonen Modallogiken wie Moores autoepistemischer Logik (AEL) und McDermotts NML-2. Wir zeigen, dass unsere Logik zwischen AEL und NML-2 liegt. Schliesslich koppeln wir die entworfene Modallogik mit der dreiwertigen Logik. Die dabei enstehende Logik MKT ist eine Erweiterung des nichtmonotonen Fragments von Belnaps Logik. Wir schliessen unsere Betrachtungen mit einem Vergleich von MKT und verschiedenen informationstheoretischen Logiken, wie z.B. Nelsons N und Heytings intuitionistischer Logik ab.

This thesis is broadly concerned with online-optimizing anti-windup control. These are control structures that implement some online-optimization routines to compensate for the windup effects in constrained control systems. The first part of this thesis examines a general framework for analyzing robust preservation in anti-windup control systems. This framework - the robust Kalman conjecture - is defined for the robust Lur’e problem. This part of the thesis verifies this conjecture for first-order plants perturbed by various norm-bounded unstructured uncertainties. Integral quadratic constraint theory is exploited to classify the appropriate stability multipliers required for verification in these cases. The remaining part of the thesis focusses on accelerated gradient methods. In particular, tight complexity-certificates can be obtained for the Nesterov gradient method, which makes it attractive for implementation of online-optimizing anti-windup control. This part of the thesis presents a proposed algorithm that extends the classical Nesterov gradient method by using available secant information. Numerical results demonstrating the efficiency of the proposed algorithm are analysed with the aid of performance profiles. As the objective function becomes more ill-conditioned, the proposed algorithm becomes significantly more efficient than the classical Nesterov gradient method. The improved performance bodes well for online-optimization anti-windup control since ill-conditioning is common place in constrained control systems. In addition, this thesis explores another subcategory of accelerated gradient methods known as Barzilai-Borwein gradient methods. Here, two algorithms that modify the Barzilai-Borwein gradient method are proposed. Global convergence of the proposed algorithms for all convex functions is established by using discrete Lyapunov theorems.