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.

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.

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.

In this thesis, a particular class of agent is singled out for examination. In order to provide a guiding metaphor, we speak of control room agents. Our focus is on rational decision- making by such agents, where the circumstances obtaining are such that rationality is bounded. Control room agents, whether human or non-human, need to reason and act in a changing environment with only limited information available to them. Determining the current state of the environment is a central concern for control room agents if they are to reason and act sensibly. A control room agent cannot plan its actions without having an internal representation (epistemic state) of its environment, and cannot make rational decisions unless this representation, to some level of accuracy, reflects the state of its environment. The focus of this thesis is on three aspects regarding the epistemic functioning of a control room agent: 1. How should the epistemic state of a control room agent be represented in order to facilitate logical analysis? 2. How should a control room agent change its epistemic state upon receiving new information? 3. How should a control room agent combine available information from different sources? In describing the class of control room agents as first-order intentional systems hav- ing both informational and motivational attitudes, an agent-oriented view is adopted. The central construct used in the information-theoretic approach, which is qualitative in nature, is the concept of a templated ordering. Representing the epistemic state of a control room agent by a (special form of) tem- plated ordering signals a departure from the many approaches in which only the beliefs of an agent are represented. Templated orderings allow for the representation of both knowledge and belief. A control room agent changes its epistemic state according to a proposed epistemic change algorithm, which allows the agent to select between two well-established forms of belief change operations, namely, belief revision and belief update. The combination of (possibly conflicting) information from different sources has re- ceived a lot of attention in recent years. Using templated orderings for the semantic representation of information, a new family of purely qualitative merging operations is developed. / School of Computing / Ph. D. (Computer Science)

In this thesis, a particular class of agent is singled out for examination. In order to provide a guiding metaphor, we speak of control room agents. Our focus is on rational decision- making by such agents, where the circumstances obtaining are such that rationality is bounded. Control room agents, whether human or non-human, need to reason and act in a changing environment with only limited information available to them. Determining the current state of the environment is a central concern for control room agents if they are to reason and act sensibly. A control room agent cannot plan its actions without having an internal representation (epistemic state) of its environment, and cannot make rational decisions unless this representation, to some level of accuracy, reflects the state of its environment. The focus of this thesis is on three aspects regarding the epistemic functioning of a control room agent: 1. How should the epistemic state of a control room agent be represented in order to facilitate logical analysis? 2. How should a control room agent change its epistemic state upon receiving new information? 3. How should a control room agent combine available information from different sources? In describing the class of control room agents as first-order intentional systems hav- ing both informational and motivational attitudes, an agent-oriented view is adopted. The central construct used in the information-theoretic approach, which is qualitative in nature, is the concept of a templated ordering. Representing the epistemic state of a control room agent by a (special form of) tem- plated ordering signals a departure from the many approaches in which only the beliefs of an agent are represented. Templated orderings allow for the representation of both knowledge and belief. A control room agent changes its epistemic state according to a proposed epistemic change algorithm, which allows the agent to select between two well-established forms of belief change operations, namely, belief revision and belief update. The combination of (possibly conflicting) information from different sources has re- ceived a lot of attention in recent years. Using templated orderings for the semantic representation of information, a new family of purely qualitative merging operations is developed. / School of Computing / Ph. D. (Computer Science)